# Why are lists the data structure of choice in functional languages?

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.

• Possible duplicate of Why are cons lists associated with functional programming? – gnat Sep 4 '17 at 11:15
• @gnat - this is not a duplicate of that question. The accepted and correct answer to that question is essentially "because an immutable linked list allows sharing tails between updated and original lists", an answer which is pointed to as part of the background to this question... – Jules Sep 4 '17 at 11:24
• One point of clarification is that a "list" (the abstract programming concept) is distinct from a "linked list" (a particular implementation of that concept), much like the specification of a programming language is distinct from its implementation. The question "why do functional languages use lists (the abstract programming concept) as their main data structure?" is subtly but fundamentally very different from the question "why do the common implementations of functional languages X, Y, & Z use linked lists as their main data structure?" – R.M. Sep 4 '17 at 16:07
• I scala Vector (which is implemented as a tree) is slightly preferred to List stackoverflow.com/questions/6928327/… In practice most people still use Lists (from what I have seen). – Akavall Sep 4 '17 at 16:32
• I did some course Functional Programming courses in Scala and used a LOT with trees. It is just that list are simpler for examples. Trees are used for performance problems. You can create inmutable trees reusing part of older trees just as you add elements to inmutable lists. – Borjab Sep 4 '17 at 18:26

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.

• Yes, Clojure vectors are implemented as trees—but it bears noting that they are hash array mapped tries, not your standard binary `data Tree a = Leaf a | Branch a (Tree a) (Tree a)`s. This reinforces your "simplicity" argument. – wchargin Sep 4 '17 at 15:38
• FWIW Clojure's persistent vectors are implemented as (as @wchargin points out somewhat complex) trees for fast (logarithmic with a large base) access and update of arbitrary elements, not really for parallel operation per se (the immutable part takes care of that to some degree). Other FP languages make the same choice (sometimes with different kinds of trees) when they want both of those (e.g. Haskell's `Sequence` or Scala's `Vector`), but don't use trees when they only need read since they can achieve that in true constant time (e.g. Haskell's `Vector` or F# via .Net's `ImmutableArray`) – badcook Sep 4 '17 at 18:13
• E.g. `pmap`ping over a vector in Clojure still accesses each element sequentially; the tree structure of the vector is generally hidden from the end user. – badcook Sep 4 '17 at 18:20

Actually, those lists are trees! You have nodes with two fields, `car` and `cdr`, which can contain more such nodes, or leaves. The only thing that makes those trees into lists, is the convention to interpret the `cdr` link as a link to the next node in a linear list, and the `car` link as the value of the current node.

That said, I guess that the prevalence of linked lists in functional programming is linked to the prevalence of recursion over iteration. When your only looping construct at hand is (tail-)recursion, you want data structures that are easy to use with that; and linked lists are perfect for that.

• that depends on the language. Sure, you can implement a tree in LISP-likes using cons cells, but in Haskell, for example, you'll need an entirely separate structure. And also note that most functional languages have a lot more looping constructs than tail recursion. The Haskell core libraries, for instance, provide folds (left and right), scans, traversals over trees, iterations over keys and values of maps, and many other more specialist structures. Sure, they're implemented with recursion behind the scenes, but the user doesn't need to even think about that to make them work. – Jules Sep 4 '17 at 15:31
• @Jules Nevertheless, functional programming was developed and highly influenced by languages like LISP. Obviously, it is possible to make all this list-iteration more efficient by using arrays under the hood, or to add syntactic sugar that hides the nature of a list, but pure functional programming can do, and does without. Also, Haskell is a pretty recent language (32 years younger than LISP), that adds quite a bit of other ideas, syntactic sugar, etc. to the pure functional style. I think, judging functional programming by judging Haskell is a bit like judging mixers by judging thermomix... – cmaster Sep 4 '17 at 15:53
• @cmaster while Haskell is younger it is still 27 years old and influenced many languages (including Python, Java and C# to name few influential). Judging functional programming by LISP is like judging imperative programming by ALGOL - both come a long way since than to become unrecognizable. OK. Lisp is arguably still relevant but I wouldn't consider it 'mainstream' and misses a lot of later insight including ML types. – Maciej Piechotka Sep 4 '17 at 18:00
• You can't process singly linked trees tail recursively or iteratively without an explicit stack if you want to touch the entire tree, so I don't think tail recursion has anything to do with it. – k_g Sep 4 '17 at 19:31
• @MaciejPiechotka Neither Python, Java, nor C# can be seen as functional languages, they are imperative and add a few features that are inspired by functional programming. Once you have changing state, you are firmly inside the domain of imperative, not functional programming. I agree with you, though, that LISP is definitely not mainstream. – cmaster Sep 5 '17 at 8:34