loading...

De-throning the List: Summary

robinheghan profile image Robin Heggelund Hansen ・2 min read

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!

Discussion

pic
Editor guide
Collapse
herteby profile image
Simon Herteby

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.

Collapse
robinheghan profile image
Robin Heggelund Hansen Author

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

Collapse
herteby profile image
Simon Herteby

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
Collapse
nmsmith profile image
Nick Smith

I'm curious about what happened to this quest. Is it still in progress?

Collapse
robinheghan profile image
Robin Heggelund Hansen Author

It's on hold for now. I'm planning to get to it, but I'm trying to finish up my work on a Elm Hashmap implementation.