Why do Haskell and Scheme use singly-linked lists?

Question

A doubly linked list has minimal overhead (just another pointer per cell), and allows you to append to both ends and go back and forth and generally have a lot of fun.

Answer 1

Well, if you look a bit deeper, both actually include arrays in the base language as well:

• The 5th revised Scheme Report (R5RS) includes the vector type, which are fixed-size integer-indexed collections with better than linear time for random access.
• The Haskell 98 Report has an array type as well.

Functional programming instruction, however, has long emphasized single-linked lists over arrays or double-linked lists. Quite likely overemphasized, in fact. There are several reasons for it, however.

First one is that single-linked lists are one of the simplest and yet most useful recursive data types. A user-defined equivalent of Haskell's list type can be defined like this:

data List a           -- A list with element type `a`...
  = Empty             -- is either the empty list...
  | Cell a (List a)   -- or a pair with an `a` and the rest of the list. 

The fact that lists are a recursive data type means that the functions that work on lists generally use structural recursion. In Haskell terms: you pattern match on the list constructors, and you recurse on a subpart of the list. In these two basic function definitions, I use the variable as to refer to the tail of the list. So note that the recursive calls "descend" down the list:

map :: (a -> b) -> List a -> List b
map f Empty = Empty
map f (Cell a as) = Cell (f a) (map f as)

filter :: (a -> Bool) -> List a -> List a
filter p Empty = Empty
filter p (Cell a as)
    | p a = Cell a (filter p as)
    | otherwise = filter p as

This technique guarantees that your function will terminate for all finite lists, and also is a good problem-solving technique—it tends to naturally splits problems into simpler, more tenable subparts.

So single-linked lists are probably the best data type to introduce students to these techniques, which are very important in functional programming.

The second reason is less of a "why single-linked lists" reason, but more of a "why not double-linked lists or arrays" reason: those latter data types often call for mutation (modifiable variables), which functional programming very often shies away from. So as it happens:

• In an eager language like Scheme you can't make a double-linked list without using mutation.
• In a lazy language like Haskell you can make a double-linked list without using mutation. But whenever you make a new list based off that one, you are forced to copy most if not all of the structure of the original. Whereas with single-linked lists you can write functions that use "structure sharing"—new lists can reuse the cells of old lists when appropriate.
• Traditionally, if you used arrays in an immutable manner it meant that every time you wanted to modify the array you had to copy the whole thing. (Recent Haskell libraries like vector, however, have found techniques that greatly improve on this problem).

The third and final reason applies to lazy languages like Haskell primarily: lazy single-linked lists, in practice, are often more similar to iterators than to in-memory lists proper. If your code is consuming the elements of a list sequentially and throwing them out as you go, the object code will only materialize the list cells and its contents as you step forward through the list.

This means that the whole list doesn't need to exist in memory at once, only the current cell. Cells before the current one can be garbage collected (which wouldn't be possible with a double-linked list); cells later than the current one don't need to be computed until you get there.

It goes even further than that. There's technique used in several popular Haskell libraries, called fusion, where the compiler analyzes your list-processing code and spots intermediate lists that are being generated and consumed sequentially and then "thrown away." With this knowledge, the compiler can completely eliminate the memory allocation of those lists' cells. This means that a single-linked list in a Haskell source program, after compilation, might actually get turned into a loop instead of a data structure.

Fusion is also the technique that the aforementioned vector library uses to generate efficient code for immutable arrays. Same goes for the extremely popular bytestring (byte arrays) and text (Unicode strings) libraries, that were built as a replacement for Haskell's not-very-great native String type (which is the same as [Char], single-linked list of character). So in modern Haskell there is a trend where immutable array types with fusion support are becoming very common.

List fusion is facilitated by the fact that in a single-linked list you can go forward but never backwards. This brings up a very important theme in functional programming: using the "shape" of a data type to derive the "shape" of a computation. If you want to process elements sequentially a single-linked list is a data type that, when you consume it with structural recursion, gives you that access pattern very naturally. If you want to use a "divide and conquer" strategy to attack a problem, then tree data structures tend to support that very well.

A lot of people drop out of the functional programming wagon early on, so they get exposure to the single-linked lists but not to the more advanced underlying ideas.

Answer 2

Because they work well with immutability. Suppose you have two immutable lists, [1, 2, 3] and [10, 2, 3]. Represented as singly linked lists where each item in the list is a node containing the item and a pointer to the rest of the list, they'd look like this:

node -> node -> node -> empty
 1       2       3

node -> node -> node -> empty
 10       2       3

See how the [2, 3] portions are identical? With mutable data structures, they're two different lists because code writing new data to one of them needs to not affect code using the other one. With immutable data however, we know that the contents of the lists will never change and code can't write new data. So we can re-use the tails and have the two lists share part of their structure:

node -> node -> node -> empty
 1      ^ 2       3
        |
node ---+
 10

Since code using the two lists will never mutate them, we never have to worry about changes to one list affecting the other. This also means that when adding an item to the front of the list, you don't have to copy and make a whole new list.

However, if you try and represent [1, 2, 3] and [10, 2, 3] as doubly linked lists:

node <-> node <-> node <-> empty
 1       2       3

node <-> node <-> node <-> empty
 10       2       3

Now the tails aren't identical anymore. The first [2, 3] has a pointer to 1 at the head, but the second has a pointer to 10. Additionally, if you want to add a new item to the head of the list you have to mutate the previous head of the list to make it point to the new head.

The multiple heads problem could potentially be fixed by having each node store a list of known heads and having the creation of new lists modify that, but then you have to work in maintaining that list to garbage collection cycles when versions of the list with different heads have different lifetimes due to being used in different pieces of code. It adds complexity and overhead, and most of the time it's not worth it.

Answer 3

@sacundim's answer is mostly true, but there are also some other important insights on trade off about language designs and practical requirements.

Objects and references

These languages usually mandate (or assume) objects having unbound dynamic extents (or in C's parlance, lifetime, although not the exact same due to the differences of meaning of objects among these languages, see below) by default, avoiding first-class references (e.g. object pointers in C) and unpredictable behavior in the semantic rules (e.g. ISO C's undefined behavior concerned with semantics).

Further, the notion of (first-class) objects in such languages is conservatively restrictive: nothing "locative" properties are specified and guaranteed by default. This is completely different in some ALGOL-like languages whose objects are without unbound dynamic extents (e.g. in C and C++), where objects basically mean some sorts of "typed storage", usually coupled with memory locations.

To encode storage within the objects has some additional benefits like being able to attach deterministic computational effects throughout their lifetime, but it is another topic.

Problems of data structures simulation

Without first-class references, singly-linked lists cannot simulate many traditional (eager/mutable) data structures effectively and portably, due to the nature of the representation of these data structures and the limited primitive operations in these languages. (On the contrary, in C, you can derive linked lists quite easily even in a strictly conforming program.) And such alternative data structures like arrays/vectors do have some superior properties compared to singly-linked lists in practice. That's why R⁵RS introduce new primitive operations.

But there do exist differences vector/array types vs. doubly-linked lists. An array is often assumed with O(1) access time complexity and less space overhead, which are excellent properties not shared by lists. (Although strictly speaking, neither is guaranteed by ISO C, but users almost always expect it and no practical implementation would violate these implicit guarantees too obviously.) OTOH, a doubly-linked list often make both properties even worse than a singly-linked list, while the backward/forward iteration are also supported by an array or a vector (together with integer indices) with even less overhead. Thus, a doubly-linked list does not perform better in general. Even worse still, the performance about cache efficiency and latency on dynamic memory allocation of lists are catastrophically worse than the performance for arrays/vectors when using the default allocator provided by the underlying implementation environment (e.g. libc). So without a very specific and "clever" runtime heavily optimizing such object creations, array/vector types are often preferred to linked lists. (For example, using ISO C++, there is a caveat that std::vector should be preferred to std::list by default.) Thus, to introduce new primitives to specifically support (doubly-)linked lists is definitely not so beneficial as to support array/vector data structures in practice.

To be fair, lists still have some specific properties better than arrays/vectors:

• Lists are node-based. Removing elements from lists does not invalidate reference to other elements in other nodes. (This is also true for some tree or graph data structures.) OTOH, arrays/vectors can make references to the trailing position being invalidated (with massive reallocation in some cases).
• Lists can splice in O(1) time. Reconstruction of new arrays/vectors with current ones are far more costly.

However, these properties are not too important for a language with built-in singly-linked lists support, which is already capable of such use. Although there still exist differences, in languages with mandated dynamic extents of objects (which usually means there is a garbage collector keeping the dangling references away), invalidation can be also less important, depending on the intents. So, the only cases where doubly-linked lists win can be:

• Both non-reallocation guarantee and bidirectional iteration requirements are needed. (If the performance of element access is important and the set of data is large enough, I'd choose binary search trees or hash tables instead.)
• Efficient bidirectional splice operations are needed. This is considerably rare. (I only meet the requirements only on implementing something like linear history records in a browser.)

Immutability and aliasing

In a pure language like Haskell, objects are immutable. Scheme's object are often used without mutation. Such fact makes it possible to effectively improve the memory efficiency with object interning - implicit sharing of multiple objects with same value on the fly.

This is an aggressive high-level optimization strategy in the language design. However, this does involve problems of implementation. It actually introduces implicit aliases to underlying storage cells. It makes aliasing analysis more difficult. As a result, there may be likely less possibilities to eliminate the overhead of non-first-class references, even users never touch them at all. In languages like Scheme, once the mutation is not totally ruled out, this also interferes parallelism. It may be OK in a lazy language (which already has performance problems caused by thunks anyway), though.

For general-purposed programming, such choice of language design may be problematic. But with some common functional coding patterns, the languages seem still work well.