Functional linked lists in Python

Inspiration

The excellent book Programming in Scala inspired me to play with functional programming concepts in Python. I ended up implementing a basic linked list data structure using a Lisp-like functional style that I want to share with you.

I wrote most of this using Pythonista on my iPad. Pythonista is a Python IDE-slash-scratchpad and surprisingly fun to work with. It’s great when you’re stuck without a laptop and want to explore some CS fundamentals :)

So without further ado, let’s dig into the implementation.

Constructing linked lists

Our linked list data structure consists of two fundamental building blocks: Nil and cons. Nil represents the empty list and serves as a sentinel for longer lists. The cons operation extends a list at the front by inserting a new value.

The lists we construct using this method consist of nested 2-tuples. For example, the list [1, 2, 3] is represented by the expression cons(1, cons(2, cons(3, Nil))) which evaluates to the nested tuples (1, (2, (3, Nil))).

Nil = None

def cons(x, xs=Nil):
    return (x, xs)

assert cons(0) == (0, Nil)
assert cons(0, (1, (2, Nil))) == (0, (1, (2, Nil)))

Why should we use this structure?

First, the cons operation is deeply rooted in the history of functional programming. From Lisp’s cons cells to ML’s and Scala’s :: operator, cons is everywhere – you can even use it as a verb.

Second, tuples are a convenient way to define simple data structures. For something as simple as our list building blocks, we don’t necessarily have to define a proper class. Also, it keeps this introduction short and sweet.

Third, tuples are immutable in Python which means their state cannot be modified after creation. Immutability is often a desired property because it helps you write simpler and more thread-safe code. I like this article by John Carmack where he shares his views on functional programming and immutability.

Abstracting away the tuple construction using the cons function gives us a lot of flexibility on how lists are represented internally as Python objects. For example, instead of using 2-tuples we could store our elements in a chain of anonymous functions with Python’s lambda keyword.

def cons(x, xs=Nil):
    return lambda i: x if i == 0 else xs

To write simpler tests for more complex list operations we’ll introduce the helper function lst. It allows us to define list instances using a more convenient syntax and without deeply nested cons calls.

def lst(*xs):
    if not xs:
        return Nil
    else:
        return cons(xs[0], lst(*xs[1:]))

assert lst() == Nil
assert lst(1) == (1, Nil)
assert lst(1, 2, 3, 4) == (1, (2, (3, (4, Nil))))

Basic operations

All operations on linked lists can be expressed in terms of the three fundamental operations head, tail, and is_empty.

• head returns the first element of a list.
• tail returns a list containing all elements except the first.
• is_empty returns True if the list contains zero elements.

You’ll see later that these three operations are enough to implement a simple sorting algorithm like insertion sort.

def head(xs):
    return xs[0]

assert head(lst(1, 2, 3)) == 1

def tail(xs):
    return xs[1]

assert tail(lst(1, 2, 3, 4)) == lst(2, 3, 4)

def is_empty(xs):
    return xs is Nil

assert is_empty(Nil)
assert not is_empty(lst(1, 2, 3))

Length and concatenation

The length operation returns the number of elements in a given list. To find the length of a list we need to scan all of its n elements. Therefore this operation has a time complexity of O(n).

def length(xs):
    if is_empty(xs):
        return 0
    else:
        return 1 + length(tail(xs))

assert length(lst(1, 2, 3, 4)) == 4
assert length(Nil) == 0

concat takes two lists as arguments and concatenates them. The result of concat(xs, ys) is a new list that contains all elements in xs followed by all elements in ys. We implement the function with a simple divide and conquer algorithm.

def concat(xs, ys):
    if is_empty(xs):
        return ys
    else:
        return cons(head(xs), concat(tail(xs), ys))

assert concat(lst(1, 2), lst(3, 4)) == lst(1, 2, 3, 4)

Last, init, and list reversal

The basic operations head and tail have corresponding operations last and init. last returns the last element of a non-empty list and init returns all elements except the last one (the initial elements).

def last(xs):
    if is_empty(tail(xs)):
        return head(xs)
    else:
        return last(tail(xs))

assert last(lst(1, 3, 3, 4)) == 4

def init(xs):
    if is_empty(tail(tail(xs))):
        return cons(head(xs))
    else:
        return cons(head(xs), init(tail(xs)))

assert init(lst(1, 2, 3, 4)) == lst(1, 2, 3)

Both operations need O(n) time to compute their result. Therefore it’s a good idea to reverse a list if you frequently use last or init to access its elements. The reverse function below implements list reversal, but in a slow way that takes O(n²) time.

def reverse(xs):
    if is_empty(xs):
        return xs
    else:
        return concat(reverse(tail(xs)), cons(head(xs), Nil))

assert reverse(Nil) == Nil
assert reverse(cons(0, Nil)) == (0, Nil)
assert reverse(lst(1, 2, 3, 4)) == lst(4, 3, 2, 1)
assert reverse(reverse(lst(1, 2, 3, 4))) == lst(1, 2, 3, 4)

Prefixes and suffixes

The following operations take and drop generalize head and tail by returning arbitrary prefixes and suffixes of a list. For example, take(2, xs) returns the first two elements of the list xs whereas drop(3, xs) returns everything except the last three elements in xs.

def take(n, xs):
    if n == 0:
        return Nil
    else:
        return cons(head(xs), take(n-1, tail(xs)))

assert take(2, lst(1, 2, 3, 4)) == lst(1, 2)

def drop(n, xs):
    if n == 0:
        return xs
    else:
        return drop(n-1, tail(xs))

assert drop(1, lst(1, 2, 3)) == lst(2, 3)
assert drop(2, lst(1, 2, 3, 4)) == lst(3, 4)

Element selection

Random element selection on linked lists doesn’t really make sense in terms of time complexity – accessing an element at index n requires O(n) time. However, the element access operation apply is simple to implement using head and drop.

def apply(i, xs):
    return head(drop(i, xs))

assert apply(0, lst(1, 2, 3, 4)) == 1
assert apply(2, lst(1, 2, 3, 4)) == 3

More complex examples

The three basic operations head, tail, and is_empty are all we need to implement a simple (and slow) sorting algorithm like insertion sort.

def insert(x, xs):
    if is_empty(xs) or x <= head(xs):
        return cons(x, xs)
    else:
        return cons(head(xs), insert(x, tail(xs)))

assert insert(0, lst(1, 2, 3, 4)) == lst(0, 1, 2, 3, 4)
assert insert(99, lst(1, 2, 3, 4)) == lst(1, 2, 3, 4, 99)
assert insert(3, lst(1, 2, 4)) == lst(1, 2, 3, 4)

def isort(xs):
    if is_empty(xs):
        return xs
    else:
        return insert(head(xs), isort(tail(xs)))

assert isort(lst(1, 2, 3, 4)) == lst(1, 2, 3, 4)
assert isort(lst(3, 1, 2, 4)) == lst(1, 2, 3, 4)

The following to_string operation flattens the recursive structure of a given list and returns a Python-style string representation of its elements. This is useful for debugging and makes for a nice little programming exercise.

def to_string(xs, prefix="[", sep=", ", postfix="]"):
    def _to_string(xs):
        if is_empty(xs):
            return ""
        elif is_empty(tail(xs)):
            return str(head(xs))
        else:
            return str(head(xs)) + sep + _to_string(tail(xs))
    return prefix + _to_string(xs) + postfix

assert to_string(lst(1, 2, 3, 4)) == "[1, 2, 3, 4]"

Where to go from here

This article is more of a thought experiment than a guide on how to implement a useful linked list in Python. Keep in mind that the above code has severe restrictions and is not fit for real life use. For example, if you use this linked list implementation with larger example lists you’ll quickly hit recursion depth limits (CPython doesn’t optimize tail recursion).

I spent a few fun hours playing with functional programming concepts in Python and I hope I inspired you to do the same. If you want to explore functional programming in ‘real world’ Python check out the following resources:

• The Python Functional Programming HOWTO
• Charming Python: Functional programming in Python
• Mike Müller’s PyCon talk: Functional programming with Python