De-throning the List: Summary

#elm

I've written a total of five posts (or six, including this one) about why I would like to replace the List with Array. If you'd missed one, here they all are:

These posts lists a ton of work. First we need to alter the Array implementation to improve performance in even more cases. Then we need to make it more extensible by introducing stoppable fold operations. Then we need to add functions that currently exists for List, but not for Array. Finally, we can make the Elm compiler output a literal representation of Array directly in the javascript code.

But why do all this work? Because I honestly believe Elm becomes easier to learn if the default collection type not only works similarly to the default collection type in other languages, but also provides decent performance for most cases you wish to use it with. I also believe Elm will become faster in the general case, if Array is used in all the places List is used today.

I might not be right. But I do think it will be an undertaking worth taking. Or... Uh... You know what I mean.

The next and first step of this journey will be to upgrade the Array implementation from being a HAMT to an RRB-Tree. This process will probably take a while, but expect a new blog post with benchmark results when it happens.

Thank you for reading!

Top comments (5)

Simon Herteby • Nov 30 '18

Excited about not having to think about Lists vs Arrays in the future!

Some of the first things I did when learning Elm was hacking together functions for getting items and deleting items by index from a List, because I hadn't looked into the Array package 😅Having Arrays as the default would have made the experience much smoother.

Btw, why is there no "delete element at index" function built in? Is it perhaps because it can "fail silently"? Ie:
I have an Array of length 3
I do some math wrong and delete index 5 instead of 2
I get the same Array of length 3 back, with no compiler error.

Robin Heggelund Hansen • Nov 30 '18

Mostly because it’s inefficient, but that might be fixed in the future

Simon Herteby • Dec 4 '18

Ah I see. Surely it'll be more efficient than people writing their own though. Here's mine 😅

remove : Int -> List a -> List a
remove index list =
    list
        |> List.indexedMap Tuple.pair
        |> List.filter (\( i, _ ) -> i /= index)
        |> List.map Tuple.second