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.
asked Sep 4, 2017 at 11:11
-
Possible duplicate of Why are cons lists associated with functional programming?– gnatSep 4, 2017 at 11:15
-
10@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...– JulesSep 4, 2017 at 11:24
-
9One 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, 2017 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).– AkavallSep 4, 2017 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.– BorjabSep 4, 2017 at 18:26
|
Show 1 more comment
2 Answers
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.
answered Sep 4, 2017 at 11:47
-
10Yes, 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.– wcharginSep 4, 2017 at 15:38 -
1FWIW 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
Sequenceor Scala'sVector), but don't use trees when they only need read since they can achieve that in true constant time (e.g. Haskell'sVectoror F# via .Net'sImmutableArray)– badcookSep 4, 2017 at 18:13 -
1E.g.
pmapping over a vector in Clojure still accesses each element sequentially; the tree structure of the vector is generally hidden from the end user.– badcookSep 4, 2017 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.
answered Sep 4, 2017 at 13:45
cmaster - reinstate monicacmaster - reinstate monica
7,8531 gold badge21 silver badges25 bronze badges
-
5that 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.– JulesSep 4, 2017 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... Sep 4, 2017 at 15:53
-
2@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. Sep 4, 2017 at 18:00
-
1You 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_gSep 4, 2017 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. Sep 5, 2017 at 8:34