J. Waldmann, March 9, 2017.

It seems that the designers of the programming language Haskell were madly in love with singly linked lists. They even granted notational privileges: e.g., the data constructor for a non-empty list ("cons") uses just one letter (`:`

) Looking at the Haskell standard, it also seems that singly linked lists are more important than the concept of static typing. When declaring the type of an identifier, we must use two letters `::`

, because the natural (that is, mathematical) notation `:`

is taken. Also, note that the list type constructor has just two letters (`[ ]`

). Can you guess Haskell's type with the next shortest name (hint: three letters)?

One goal of language design is to make typical expected usage easy to write. Once the design is cast in stone, this becomes self-fulfilling: unsuspecting users of the language will write programs in what they think is idiomatic style, as suggested by built-in syntactical convenience. So it seems that it is typical Haskell to: not declare types for identifiers, and use machine numbers and lists all over the place.

This, with the lists, I mean, needs to stop. Now.

Lists do have their purpose, but it's rather limited. In fact, there is just one:

*iteration*: you use each element of a collection*in order*(FIFO or LIFO), on demand, and at most once.

If you use lists for anything else, in particular

*storage*: you use elements*out of order*, e.g., by known index, or you access ("search") elements by a property,

then you're doing it wrong, *wrong*, *wrong*. I will explain why, and what you should do instead.

As an appetizer, here are some bumper-sticker slogans extracted from the sections that follow.

- If your program accesses a list by index (with the
`!!`

operator), then your program is wrong. - If your program uses the
`length`

function, then your program is wrong. - If your program sorts a list, then your program is wrong.
- If you wrote this
`sort`

function yourself, then it is doubly wrong. - The ideal use of a list is such that will be removed by the compiler.
- The enlightened programmer writes list-free code with
`Foldable`

.

Sounds unbelievable? Read on!

Certainly Haskell builds on the legacy of LISP, the very first functional programming language - that has lists in its name already. Indeed, singly linked lists were the only way to structure nested data in LISP.

This is a huge advantage (it's soo uniform), but also a huge dis-advantage (you cannot distinguish data - they all look like nested lists). For discriminating between different shapes of nested data, people then invented algebraic data types, pattern matching, and static typing. The flip side of static typing is that it seems to hinder uniform data processing. So, language designers invented polymorphism (type constructors) and generic programming, to get back flexibility and uniformity, while keeping static safety.

This was all well known at the time of Haskell's design, so why are lists that prominent in the language? The one major design goal for Haskell was: to define a functional programming language with static typing and *lazy evaluation*. For functional programming with static typing and strict evaluation, the language ML was already well established, cf. D. A. Turner: Some History of Functional Programming Languages. Haskell has lazy evaluation for function calls, including constructor applications, and a prime showcase for this is that we can handle apparently infinite data, like streams:

`data Stream a = Cons a (Stream a)`

Such streams do never end, but we can still do reasonable things with them, by evaluating finite prefixes on demand, in other words, lazily.

Now a standard Haskell list is just such a stream that *can* end, because there is an extra constructor for the empty stream

`data Stream a = Nil | Cons a (Stream a)`

and the problem with Haskell lists is that people tend to confuse what the type `[ a ]`

stands for:

- is it: lazy infinite stream (yes)
- or is it: finite list (no).

If you have an object-oriented background, then this can be phrased as the confusion

- between an iterator (that allows to traverse data)
- and its underlying collection (that holds the actual data).

A Haskell list is a very good iterator - we even might say, it is the *essence* of iteration, but it makes for a very bad implementation of a collection.

The (historic) first impression of "functional programming is inherently list processing" seems hard to erase. Indeed it is perpetuated by some Haskell teaching texts, some of which are popular. If a text(book) aimed at beginners presents `Int`

, `String`

and `[Int]`

on pages 1, 2, 3; but keywords `data`

and `case`

(and assorted concepts of algebraic data type and pattern matching) appear only after the first two hundred pages, well, then something's wrong.

For example, the shiny new http://haskell.org/ gets this exactly wrong. At the very top of the page, it presents example code that is supposed to highlight typical features of the language. We see a version of Eratosthenes' sieve that generates an infinite list of primes. Declarative it certainly is. But see - Lists, numbers. Must be typical Haskell.

Also, that example code features list comprehensions - that's more syntactic sugar to misguide beginners. And it claims "statically typed code" in the previous line, but - there is no type annotation in the code. Yes, I know, the types are still there, because they are inferred by the compiler, but what does a beginner think?

The icing on all this is that the one thing that this example code really exemplifies, namely: infinite streams with lazy evaluation, is not mentioned anywhere in the vicinity.

The answer is simple: *never use lists for data storage with out-of-order access.*

Accessing an element of a singly linked list at some arbitrary position *i* takes time proportional to *i*, and you do not want that.

The only operation that's cheap with a singly linked list is accessing its first element element (the head of list), and prepending a fresh first element.

So can we access any of the other elements in any reasonable way? Yes, we can access the second element, but only after we drop the first one. The second element becomes the "new head", and the "old head" is then gone for good. We are singly linked, we cannot go back. If we want to access any element in a list, we have to access, and then throw away, all the elements to the left of it.

In other words, lists in Haskell realize what object oriented people would call the *iterator* design pattern (Iterator

Or, we can think of a list as a stack, and going to the next element is its "pop" operation.

Can we really never go back? Well, if `xs`

is an iterator for some collection, then `x : xs`

is an iterator that first will provide `x`

, and after that, all elements of `xs`

. So, thinking of a list as a stack, the list constructor (`:`

) realizes the "push" operation.

On the other hand, the "merge" function (of "mergesort" fame, it merges two monotonically increasing sequences) is a good use case for Haskell lists, since both inputs are traversed in order (individually - globally, the two traversals are interleaved). Its source code is

```
merge :: Ord a => [a] -> [a] -> [a]
merge as@(a:as') bs@(b:bs')
| a `compare` b == GT = b:merge as bs'
| otherwise = a:merge as' bs
merge [] bs = bs
merge as [] = as
```

We never copy lists, and we only ever pattern match on their beginning.

Indeed you can easily (in Java or C#) write a `merge`

function that takes two iterators for monotone sequences, and produces one. Try it, it's a fun exercise. Use it to learn about `yield return`

in C#.

Back to Haskell: how should we implement merge-sort then, given `merge`

? The truthful answer is: we should not, see below. But for the moment, let's try anyway, as an exercise. A straightforward approach is to split long input lists at (or near) the middle:

```
msort :: Ord a => [a] -> [a]
msort [] = [] ; msort [x] = [x]
msort xs = let (lo,hi) = splitAt (div (length xs) 2) xs
in merge (msort lo) (msort hi)
```

but this is already wrong. Here, `xs`

is not used in a linear way, but twice: first in `length xs`

(to compute to position of the split), and secondly, in `splitAt ... xs`

, to actually do the split. This is inefficient, since the list is traversed twice, which costs time -- and space, since the spine of the list will be held in memory fully.

Indeed, the Haskell standard library contains an implementation of mergesort that does something different. The basic idea is

```
msort :: Ord a => [a] -> [a]
msort xs = mergeAll (map (\x -> [x]) xs)
where mergeAll [x] = x
mergeAll xs = mergeAll (mergePairs xs)
mergePairs (a:b:xs) = merge a b: mergePairs xs
mergePairs xs = xs
```

But the actual implementation has an extra provision for handling monotonic segments of the input more efficiently. Make sure to read the discussion mentioned in the comments atop the source.

But - if you sort a list in your application *at all*, then you're probably doing something wrong already. There's a good chance that your data should have *never* been stored in a list from the start.

This was *the* topic in your "Data Structures and Algorithms" course, way back. Here is a summary.

There are two exemptions from the rules stated above.

If you are positively certain that your collections have a *bounded* size throughout the lifetime of your application, then you can choose to implement it in any way you want (and even use lists), because all operations will run in constant time anyway. But beware - "the constant depends on the bound". So if the bound is three, then it's probably fine.

Then, *education*. With lists, you can exemplify pattern matching and recursion (with streams, you exemplify co-recursion). Certainly each student should see and do recursion early on in their first term.

But the teacher must make very clear that this is in the same ballpark with exercises of computing Fibonacci numbers, or implementing multiplication and exponentiation for Peano numbers: the actual output of the computation is largely irrelevant. What is relevant are the techniques they teach (algebraic data types, pattern matching, recursion, induction) because these have *broad* applications.

So, indeed, when I teach algebraic data types, I do also use singly linked lists, among other examples (Bool, Maybe, Either, binary trees), but I always write (and have students write)

`data List a = Nil | Cons a (List a)`

and I avoid Haskell's built-in lists altogether. (More on how I teach FP. And Joachim does it in a similar way.)

But, back to "real code".

We learned above that the one legitimate use case for lists is iteration. This is an important one. It's so important that the Glasgow Haskell compiler applies clever program transformations (at least since 1993, see this paper) in order to generate efficient machine code for programs that combine iterators (that is, lists) in typical ways.

The idea is that the most efficient code is always the one that is not there at all. Indeed, several program transformations in the compiler remove intermediate iterators (lists). Consider the expression

`sum $ map (\x -> x*x) [1 .. 1000]`

which contains two iterations: the list `[1 .. 1000]`

(the *producer*), and another list (of squares, built by `map`

, which is a *transformer*). Finally, we have `sum`

as a *consumer* (its output is not a list, but a number).

We note that a transformer is just a consumer (of the input list) coupled to a producer (of the output list). Now the important observation is that we can remove the intermediate list between a producer and the following consumer (where each of them may actually be part of a transformer).

This removal is called *fusion*. With fusion, lists are used prominently in the source code, but the compiler will transform this into machine code that does not mention lists *at all*! In particular, the above program will run in constant space. It allocates *nothing* on the heap, and it needs *no* garbage collector.

For historic reference and detail, see Phil Wadler: Deforestation: transforming programs to eliminate trees, 1990.

Now I will present a more recent development (in the style of writing libraries for Haskell) that aims to remove lists from the actual source code. (Recall that deforestation removes lists from compiled code.)

We have, e.g., `and [True, False, True] == False`

, and you would think that `and`

has type `[Bool] -> Bool`

(it maps a list of Booleans to a Boolean). But no, the type is `and :: Foldable t => t Bool -> Bool`

, and indeed we can apply `and`

to any object of a type `t a`

where `t`

implements `Foldable`

.

As a first approximation, `Foldable t`

means that `t`

is a type constructor (it has kind `* -> *`

) and there must be a function `toList :: t a -> [a]`

. So, `c`

of type `t a`

with `Foldable t`

can be thought of as some kind of collection, and we can get its elements by calling `toList`

. This is similar to `Iterable<A> c`

, and `toList (c)`

is `c.iterator()`

.

For example, `Data.Set`

(mentioned above) does this, so we can make a set `s = S.fromList [False, True]`

and then write `and s`

. It will produce the same result as `and (toList s)`

where this time, `and :: [Bool] -> Bool`

.

Why all this? Actually, this is not about `toList`

. Quite the contrary - this `Foldable`

class exists to make it easier to *avoid* lists. Typically, we would not implement or call the `toList`

function, but use `foldMap`

or `foldr`

instead.

We give another example. Ancient standard libraries used to have a function `sum :: Num a => [a] -> a`

but now its actual type is `sum :: (Num a, Foldable t) => t a -> a`

, and so we can take the sum of all elements in a set `s :: Set Int`

simply via `sum s`

, instead of writing `sum (toList s)`

. See - the lists are gone from the source code.

Let us look at the type of `foldMap`

, and the class `Monoid`

that it uses. (And, if you're new to Haskell, remember that `class`

here is more like `interface`

in Java - it contains method signatures)

```
class Foldable t where
foldMap :: Monoid m => (a -> m) -> t a -> m
class Monoid m where
mempty :: m
mappend :: m -> m -> m
```

This is fancy syntax for the following (slightly re-arranged)

`foldMap :: m -> (a -> m) -> (m -> m -> m) -> t a -> m`

So when you call `foldMap`

over some collection (of type `t a`

), then you have to supply the result value (`mempty :: m`

) for the empty collection, the mapping (of type `a -> m`

) to be applied to individual elements, and a binary operation (`mappend :: m -> m -> m`

) to be used to combine results for sub-collections.

Let us see how this is used to `sum`

over `Data.Set`

, the type mentioned above, repeated here for convenience:

```
data Set a = Bin Size a (Set a) (Set a)
| Tip
instance Foldable Set where
foldMap f t = go t
where go Tip = mempty
go (Bin 1 k _ _) = f k
go (Bin _ k l r) = go l `mappend` (f k `mappend` go r)
```

(actual source code) This means that `foldMap f s`

, for `s :: Set a`

of size larger than one, does the following: each branch node `n`

is replaced by two calls of `mappend`

that combine results of recursive calls in subtrees `l`

and `r`

of `n`

, and `f k`

for the key `k`

of `n`

, and we make sure to traverse the left subtree, then the key at the root, then the right subtree.

The definition of `sum`

is

```
class Foldable t where
sum :: Num a => t a -> a
sum = getSum #. foldMap Sum
```

with the following auxiliary types

```
newtype Sum a = Sum { getSum :: a }
instance Num a => Monoid (Sum a) where
mempty = Sum 0
mappend (Sum x) (Sum y) = Sum (x + y)
```

(actual code) So, when we take the `sum`

of some `Set a`

, we do a computation that adds up all elements of the set, but without an explicit iterator - there is no list in sight.

I will close this section with a word of caution: when the types for `sum, and`

, and many more functions were generalized from lists to `Foldable`

a while back, some over-the top `Foldable`

instances were introduced that result in funny-looking semantics like `maximum (2,1) == 1`

, which is only "natural" if you think of the curried type constructor application `(,) a b`

, remove the last argument, and demand that `(,) a`

"obviously" must be `Functor`

, `Foldable`

, and so on. Well, this might save some people some keystrokes, but Henning says that this *moves Haskell into the Matlab league of languages* where any code is accepted, with unpredictable results. But that's a separate topic, and this page here is long enough already.

Joachim Breitner, Bertram Felgenhauer, Henning Thielemann and Serge Le Huitouze have sent helpful critique and comments on earlier versions of this text. Of course, all remaining technical errors are my own, and I do not claim the commenters endorse my views.

But I hope they do! In fact Henning already beat me to it (by several years, I guess) - read his Lists are not ....

... at reddit, ... at the Haskell Cafe (... which is not a Google group)