De-throning the List

The topic isn’t about combining , but replacing the list entirely.

No thank you - there are many data types to handle many different situations - why replace a linked list with an array in a language when it already has both and the history of computing science has provided both of us to them?

I would like to keep having choices.

1 Like

List can still be in the std lib, but it shouldn’t be the default.

1 Like

New part of the series out now. Look at the top post for link.

2 Likes

Just a silly question: in your examples you use these type annotations:
find : (a -> Bool) -> List a

instead of
find : (a -> Bool) -> List a -> Maybe a

Why is that?

1 Like

Oversight on my part. Have fixed it now. Thanks for pointing it out :slight_smile:

New part published now, see top post for link.

2 Likes

I’ve been accessing this through the email interface, and so I didn’t realize you had been editing the top post. I was beginning to get the impression that you were making a point by having us click through a linked list of articles each time. :slight_smile:

1 Like

I’ll keep that in mind for my next update :slight_smile:

In the latest post it points out that Set in Elm is ordered. Worth noting, in general Set implementations do not need to be ordered - an example being a Set based on hash tables.

If you were to build one of these ‘collections’ with Set semantics, how would you do that? The same collection implementation also supports List semantics, so they must have different constructors right? Would be interesting to see the constructor APIs.

Its an interesting piece of work you have done here, and on the whole I would be in favour of it. It will perform well enough, and is a real simplification.

1 Like

While Sets doesn’t necessarily have to be ordered to be a set, Elm’s Set is. I’m working on a HashSet for Elm right now, so there could be multiple Set implementations in the future.

The point is that Set’s are collections, and so there are multiple functions available in the List and Array API that also makes sense to implement for Set.

Excellent series. I liked the approach of speaking in broader concepts and then applying them to the current state of Elm.

I think performance concerns (especially wrt defaults) are central to Elm because Elm runs in the web browser and thus slow clients (like low-end mobile devices) cannot be avoided.

And since defaults have such a big impact on what people use, we have situations like people preferring List even though their data access patterns don’t match the List’s niche. It’s easy for us to say “well, I don’t want to have to think about datastructures,” but that comes at the expense of every client having to pay the penalty for us, like reversing a large array of endless-scroll gallery images on every render on the UI thread.

Kotlin’s solution here was to provide built-in functions like listOf(1, 2, 3), arrayOf(1, 2, 3), setOf(1, 2, 3) instead of a collection literal. Though I think there is now a generic [1, 2, 3] literal that you must explicitly annotate so it knows which collection impl to use, else it won’t compile.

Just about every time I implement a custom datastructure in Elm, I end up using an Array for its performance properties. For example, any time I need a grid of game pieces or gallery images, I often need to index into it. When I have a sequence in Elm (and UIs in general), I often am appending to the end but want to iterate in insertion order, which is precisely the List’s worst case.

If Elm were to adopt the Array as the default collection, I wonder how much of its APIs would also change. For example, ctrl-f “List” on http://package.elm-lang.org/packages/elm-lang/html/2.0.0/Html. One downside of using Array currently is that you have to convert it to a List in the view on each render though I never took the time to see what kind of perf impact it can have on a real world app.

I look forward to see what comes of this discussion.

1 Like

The last pieces of the blog series are out now:

Part Boron: https://dev.to/skinney/de-throning-the-list-part-boron-185
Summary: https://dev.to/skinney/de-throning-the-list-summary-3f3c

6 Likes

I am a little confused by this post:

Since in that one you also bring Set into the picture, but in the earlier posts you only talked about List and Array. Are you also going to try and build a data structure which can replace Set too?

That is why, above, I was asking what the constructors would look like. That is, how do you build this thing with Array vs Set semantics?

Dethroned.list [ 1, 2, 2, 3]
Dethroned.set [ 1, 2, 2, 3]

But perhaps this is not your intention and the above post has given me an incorrect understanding.

I mentioned Set because it felt natural at the time, it being a sequential collection type and all.

I don’t really see the constructors changing from how they work today. fromList would just become fromArray.

So your proposed new data structure will also support set semantics?

No.

For set semantics, you’ll still need to convert to a Set.

1 Like

Thanks for clarifying. I hope the implementation goes well for you.

FP’s extensive use of linked lists only augments the sorts of data structures you’re used to, it doesn’t replace them.

[…]

You don’t use a linked list in Haskell in a case where you’d be using an ArrayList in Java; you use a linked list in Haskell in a case where you’d be using a for loop in Java

Interesting thoughts from this article on List versus Vector / Seq in Haskell. Seems relevant to the conversation here, although I wonder if the lazy/eager distinction between Elm and Haskell makes a difference :slightly_smiling_face:

1 Like

If I read the article correctly, lazyness and compiler opts is why you can use List as a for/foreach type thing. Elm, being strict, isn’t such a good fit then.