De-throning the List
Tags: elm
Published: 2018-03-23 16:12:39

---
title: De-throning the List
published: true
description: Where I argue that the list is a bad general purpose data structure
tags: elm
---

Listen, I have a plan. What kind of a plan, you ask? A cunning one. As cunning as a fox? Yeah, I'd say so. As cunning as a cat that has trained a man to bring her food at the ring of a bell? Yeah... no. I mean, that is pretty clever. Let's instead say that I have an idea which could potentially be a very good one:

I want to remove the List.

## Hear me out

Every programming language has a general purpose collection type. Most non-functional languages, like Javascript and Java, uses an array. However, in functional languages it's not too uncommon to see a list. Why is that?

For the most part I suspect the reason is historical. Efficient immutable arrays is a pretty recent invention, first being seen in Clojure back in 2007. Popular functional languages like Haskell, OCaml and Common Lisp are from the 80's and 90's, so it simply wasn't available at the time.

In addition, the list is very simple to implement and get right. And it does have some strong suites. For instance, if you want to access the first element, remove it or even add a new first element, you can do so in constant time. You can also iterate over the collection, from left to right, in linear time, as you'd expect.

But it also has some shortcomings which can be hard to swallow. If you want to retrieve or modify any element but the first, you'll do so in linear time (yuck). If you want to iterate the items from right to left, which you have to do when performing `map` or `filter`, you'll have to reverse the list first (yes, really!).

Another thing to mention is that `List` isn't really suited for a browser environment. Let's take a look at how `[1, 2]` is compiled down to JS:

```js
{ ctor: '::', a: 1, b: { ctor: '::', a: 2, b: { ctor: '[]' } } }
```

There's a problem with this though. Once the list gets big enough, browsers (or at least Chrome) will crash due to stack overflow exception. So in Elm 0.19, this is what the same list compiles to:

```js
<core_namespace>$ToList([1, 2])
```

This is much shorter and will minify beautifully, but also means that every list literal in your application has an extra cost at runtime. An inlined `Array` wouldn't have these issues.

Because of the issues I've just mentioned, I believe `List` isn't fit to serve as the default collection type in Elm. I think `Array` would serve this role better, especially considering it works more like what people are used to from Javascript.

## So we'll replace `List` with `Array`, problem solved!

Well, not so fast.

First off, the implementation details of `Array` are hidden inside an opaque type. This is done with good reason, as `Array` is a tricky data structure to get right. But it also means that there are certain things you cannot do efficiently with an `Array`, which are trivial to do with a `List`, like filtering elements until you've found a certain amount.

The `Array` also seems to be bad at all the things a `List` is good at. For instance, if you wish to insert or remove an element at the beginning of a `List` it's a constant time operation. Doing the same with an `Array` requires re-building the entire data structure, which in comparison is horribly slow.

Finally, there are certain operations that are implemented for `List` but not for `Array`, like `sort`.

## So we're stuck with the `List` then?

That's the thing. I don't think we are. I believe all the problems I've mentioned can be solved, and that's what my cunning plan is all about.

Over the next couple of weeks I'll explain my plan in full. There will be benchmarks, code snippets and maybe even another reference to Black Adder. The plan, as sinister as it is, does require a lot of work however, so I wouldn't count on seeing it implemented any time soon.

Tune in [next time](https://dev.to/skinney/de-throning-the-list-part-deux-4idm) to see how we can make `Array` more flexible.