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:
{ 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:
<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 to see how we can make Array more flexible.
Top comments (0)