Length Matters

A linked list is an elegant data structure. In F# you can define one with a recursive discriminated union:

type LinkedList<'T> =
    | Nil
    | Cons of 'T * LinkedList<'T>

Linked lists come with some nice benefits: you can insert or remove at the head in constant time; there’s no need to resize as with arrays or vectors at max capacity and multiple lists can share the same tail structure — great in combination with immutability.

For example the snippet below will not require two allocations of the element 1.

  let x = Cons(1, Nil)
  let y = Cons(2, x)    // Shares its tail with x

While the benefits may be nice, a linked list also has several drawbacks. Compared to an array, it does not offer constant-time random access. Fetching the i’th node of a linked list requires starting from the head and visiting nodes until reaching the desired position.

Another practical issue is memory layout. Unlike an array, which stores its data in a contiguous block of memory, a linked list can have its nodes scattered across the heap. This hurts cache locality. The effect can be so dire that, even in cases where a linked list should be the theoretical best choice, an array may outperform it in practice.

For a deeper dive into this, I recommend Bjarne Stroustrup’s talk “Why You Should Avoid Linked Lists.”

When working with linked lists in a functional language, recursion is your go-to tool. A function for returning the length of a linked list can be defined as:

let length list =
    let rec lengthInner length list =
        match list with
        | Nil -> length
        | Cons(_, tail) -> lengthInner (length + 1) tail

    lengthInner 0 list


let foo = Cons(3, Cons(2, Cons(1, Nil)))
length foo // 3

Checking whether a container is empty is a very common pattern — for example:

  if arr.Length = 0 then
    // do something

Using our previously defined length we can achieve the same for our linked list.

  if length linkedList = 0 then
    // do something

This behaves like the array snippet, but there’s a subtle issue. What we really want to know is whether the list is empty i.e., if it is the Nil case. We are not actually interested in the list’s length, we only use length because an empty list has length zero.

An array stores its length as a field, so returning it is constant time. Looking at our LinkedList we have no such thing in this case. When checking if our list is empty, we are currently iterating through the whole list and then checking whether we iterated over zero Cons cases. Stopping at the first Cons case would have been enough. Our way of checking if a list is empty is O(n). Building the code in Release config, the snippet above is not optimized to a constant-time operation.

Luckily we can easily define a constant-time check for emptiness.

let isEmpty list =
  list = Nil

This runs in constant time, so we do not pay a performance penalty compared to arrays. The F# standard library provides such a function: List.isEmpty that checks whether an F# list (a linked list) is empty or not.

The point is: next time you see a call to List.length (or similar), pause and ask — do we really need the length, or just to know whether it’s empty?

You might save some CPU cycles — and the environment. :)