# Functional linked lists in Python

Linked lists are fundamental data structures that every programmer should know. This article explains how to implement a simple linked list data type in Python using a functional programming style.

## Inspiration

The excellent book Programming in Scala inspired me to play around with functional programming concepts in Python. I ended up implementing a basic linked list data structure using a Lisp-like functional style and I’d like to share it 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. I recommend it very much if you’re ever stuck without a laptop and want to explore some CS fundamentals :)

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

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 more complex lists. The `cons` operation extends a list at the front by inserting a new value.

The lists we construct using this method consist internally 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, you say?

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. Can’t be bad to stand on the shoulders of these functional giants, can it?

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. Plus it keeps this tutorial / thought experiment 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 gives a pragmatic view on functional programming / 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 using Python’s `lambda` keyword.

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

To make the tests for the following list operations slightly simpler to write we’ll introduce the helper function `lst`. That 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`. You’ll see later on that these three operations are enough to implement a simple sorting algorithm like insertion sort.

• `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.
```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, thus leading to 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 `contact(xs, ys)` is a new list that contains all elements in `xs` followed by all elements in `ys`. We implement list concatenation with a simple divide and conquer algorithm.

```def concat(xs, ys):
if is_empty(xs):
return ys
else:

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`. Calling `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)):
else:
return last(tail(xs))

assert last(lst(1, 3, 3, 4)) == 4
```
```def init(xs):
if is_empty(tail(tail(xs))):
else:

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

Both operations need O(n) time compute their result. Therefore it makes sense to reverse the list if you frequently use `last` or `init` to access list elements. The `reverse` function below implements list reversal, albeit in a slow way that takes O(n²) time.

```def reverse(xs):
if is_empty(xs):
return xs
else:

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:

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 does not really make sense in terms of time complexity, as accessing an element at index n requires O(n) time. Nevertheless, the element access operation `apply` is simple to implement using the `head` and `drop` operations.

```def apply(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 enough 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:

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:

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)):