Functional Programming – Why Are Cons Lists Associated with Functional Programming?

functional programminglinked listlistprogramming-languages

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?

Best Answer

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.

Related Topic