Functional Programming – Why Lists Are Preferred Data Structures

functional programming

Most functional languages use linked lists as their primary immutable data structure. Why lists, and not e.g. trees? Trees can also reuse paths, and even model lists.

Best Answer

Because lists are simpler than trees. (You can see this trivially by the fact that a list is a degenerate tree, where every node has only a single child.)

The cons list is the simplest possible recursive data structure of arbitrary size.

Guy Steele argued during the design of the Fortress programming language that for the massively parallel computations of the future, both our data structures and our control flow should be tree-shaped with multiple branches, not linear as they are now. But for the time being, most of our core data structure libraries were designed with sequential, iterative processing (or tail recursion, it doesn't really matter, they are the same thing) in mind, not parallel processing.

Note that e.g. in Clojure, whose data structures were designed specifically for the parallel, distributed, "cloudy" world of today, even arrays (called vectors in Clojure), probably the most "linear" data structure of them all, are actually implemented as trees.

So, in short: a cons list is the simplest possible persistent recursive data structure, and there was no need to choose a more complicated "default". Others are of course available as options, e.g. Haskell has arrays, priority queues, maps, heaps, treaps, tries, and everything you could possibly imagine, but the default is the simple cons list.

Related Solutions

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

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.

Functional Programming – Introducing Constructs in Non-Functional Languages

Notwithstanding any specific ideas on the part of language designers, it bears mentioning that authors and stewards of programming languages are, in the end, pushing a product. So, I might ask why I'd want a camera-phone when my plain phone is a better phone and my camera a better camera, but that isn't going to stop manufacturers of both devices from trying to broaden their product's offering to attract new customers.

Once you look at it from that perspective, then notions of preserving the integrity of the original language become a matter of degrees and tradeoffs. If I'm the author of OOP language AwesomeCode and I see people starting to get interested in new functional language FCode, do I tell my users "sorry, but this is an OOP language only" and risk them going to C# instead to get at its lambas, or do I cave and grudgingly include some of FCode's functionality?

Best Answer

Related Solutions

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

Functional Programming – Introducing Constructs in Non-Functional Languages

Related Topic