As we talked about last time, there are certain use cases where the Array performs horribly when compared to a List. So in this article, we'll expl...
For further actions, you may consider blocking this person and/or reporting abuse
The distinction between the start and the end of a List/Array is really arbitrary. You could consider a List to grow to the right instead of the left by just flipping the List constructors and functions:
head :: tail --> front :: last
etc, and then suddenly Lists are really fast at adding elements to the end!
Because of this, I don't think the distinction between Arrays being fast at the end and Lists being fast at the start is necessary. Really they're both fast at adding to any one predetermined end, with List being a constant factor faster (from the benchmarks, seemingly 7x). This makes Lists slightly better for an algorithm that needs to grow or shrink a List at only one end. For anything else, Lists are usually worse.
If the solution to having fast insertions at either end of an Array is RRB trees, aren't we going in circles? This is the implementation Elm has in 0.18 (though it could do with some work).
I wouldn’t say we’re going in circles. The 0.19 implementation is a complete re-write, because the 0.18 implentation is undocumented an buggy. It was always planned that it would eventually evolve into an RRB tree in time.
Fair enough. Obviously I'm not informed about those plans - they're not public I'm assuming.
I think i’ve mentioned it in my status updates in the elm-dev mailing list. It’s not secret by any means, but i’m not the authority on what makes it into Elm, so I don’t mention it often either.
Maybe you'll find some interesting details in how Purescript deals with arrays: pursuit.purescript.org/packages/pu...
This seems to be an immutable wrapper over regular js arrays, which is what the 0.19 implementation uses under the hood. Thanks for the link, though!
yes it is - and it's IMO exactly the thing to do - at least for purescript where FFI is a primary concern (yes I know Elm is moving away from anything similar - that's why purescript might get more interesting for people who want/need more that ports)
Different use cases. The thing you linked to will have horrible write performance for large arrays.
that's probably why there are the warnings at the very top ;)
if you want performance then probably finger-tree approaches (pursuit.purescript.org/packages/pu... ) are sensible ... it of course all depends on what you are trying to do
Finger trees are cool, but no replacement for a proper immutable array implementation, and they’re not general purpose enough to be the default.
The main question I have is, do you intend to remove the list pattern matching constructors [] and ::? Or will these new List/Array data types also support them?
My intent is that
[1,2,3]creates an Array instead of List, and that pattern matching is removed.x :: restwould translate into(Array.get 0 array, Array.slice 1 length array), which isn't the fastest way to do things. This is the topic of my next post.Is this for 0.19? It would be helpful to know if all code that uses List constructor pattern matching is going to be broken.
It would also be possible to keep the pattern matching, but have a compiler intrinsic for handling it in the case of Lists.
I doubt i’ll get this done before 0.19 but even if I was, i’m not a core developer so it wouldn’t be certain that this stuff made it in anyway.
Ok helpful to know, you are currently just experimenting with stuff but no particular version where it will be introduced.
I don't have much code that uses List constructor pattern matching, so it is perhaps not such a big deal if that went away. It might be worth grepping all published Elm repositories too to get a feel for how much they are used.
I come from a Java background so choosing data structure implementations is natural to me. I do remember during your talk at Elm Europe last year, a Python developer asking why Elm has so many data structure types and how to choose between them. So I do think this List/Array merge is a positive direction to go in.