Why are cons lists associated with functional programming?

Question

I have noticed that most functional languages employ a singly-linked list (a "cons" list) as their most fundamental list types. Examples include Common Lisp, Haskell and F#. This is different to mainstream languages, where the native list types are arrays.

Why is that?

For Common Lisp (being dynamically typed) I get the idea that the cons is general enough to also be the base of lists, trees, etc. This might be a tiny reason.

For statically typed languages, though, I can't find a good reasoning, I can even find counter-arguments:

• Functional style encourages immutability, so the linked list's ease of insertion is less of an advantage,
• Functional style encourages immutability, so also data sharing; an array is easier to share "partially" than a linked list,
• You could do pattern matching on a regular array just as well, and even better (you could easily fold from right to left for example),
• On top of that you get random access for free,
• And (a practical advantage) if the language is statically typed, you can employ a regular memory layout and get a speed boost from the cache.

So why prefer linked lists?

Answer 1

The most important factor is that you can prepend to an immutable singly linked list in O(1) time, which allows you to recursively build up n-element lists in O(n) time like this:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

If you did this using immutable arrays, the runtime would be quadratic because each cons operation would need to copy the whole array, leading to a quadratic running time.

Functional style encourages immutability, so also data sharing; an array is easier to share "partially" than a linked list

I assume by "partially" sharing you mean that you can take a subarray from an array in O(1) time, whereas with linked lists you can only take the tail in O(1) time and everything else needs O(n). That is true.

However taking the tail is enough in many cases. And you have to take into account that being able to cheaply create subarrays doesn't help you if you have no way of cheaply creating arrays. And (without clever compiler optimizations) there is no way to cheaply build-up an array step-by-step.

Answer 2

I think it comes down to lists being rather easily implemented in functional code.

Scheme:

(define (cons x y)(lambda (m) (m x y)))

Haskell:

data  [a]  =  [] | a : [a]

Arrays are harder and not nearly as pretty to implement. If you want them to be extremely fast then they'll have to be written low-level.

Additionally, recursion works much better on lists than arrays. Consider the number of times you've recursively consumed/generated a list vs indexed an array.

Answer 3

A singly-linked list is the simplest persistent data structure.

Persistent data structures are essential for performant, purely functional programming.

Answer 4

You can use Cons nodes easily only if you have a garbage collected language.

Cons Nodes match a lot with the functional programming style of recursive calls and immutable values. So it fits well into the mental programmer model.

And don't forget historical reasons. Why are they still called Cons Nodes and worse still use car and cdr as accessors? People learn it from text books and courses and then use it.

You are right, in the real world arrays are much easier to use, consume only half the memory space and are much performanter because of cache level misses. There is no reason to use them with imperative languages.

Answer 5

Linked lists are important for the following reason:

Once you take a number like 3, and convert it to successor sequence like succ(succ(succ(zero))), and then use substitution to it with {succ=List node with some memory space}, and {zero = end of list}, you'll end up with a linked list (of length 3).

The actual important part is numbers, substitution, and memory space and zero.