De-throning the List

Request Feedback
41

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.

42

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

43

No.

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

1 Like
44

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

45

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
46

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.

47

I guess the nice thing about lists is that with pattern matching they give a lot of flexibility on how you iterate them. It’s pretty easy to write a function that iterates two lists at the same time, but iterates the first list twice as “fast” as the second. This really also encourages the whole FP learning path around control flow, recursion and pattern matching, which are all core concepts.

If Array is the default, it will be more difficult to explain things like map and fold, since you can’t trivially show your own definition anymore.

The question in my mind is – are these problems solvable by some sort of “compiler magic”? Currently some forms of recursion (at least tail recursion) compile down to while loops, so could a similar transformation be made to support arrays in that sort of way?

3 Likes
48

It almost certainly is possible. I don’t know if :: and [] are pattern matched by the same compiler code that pattern matches type constructors - they may already be special cases in the compiler. It is then a question of capturing these special cases and generating the appropriate code to work with arrays instead of lists.

Somewhat approximately:

case l of 
  x :: xs -> ...

Translates to:

if Dethroned.size l > 1 then
  let
    x = Dethroned.head l
    xs = Dethroned.tail l
  in
    ...
49

Good points.

Since Array provides fast access time to any index, one could always implement map as:

map : (a -> b) -> Array a -> Array b
map f arr =
  let
    helper f idx len acc =
      if idx >= len then
        acc
      else
        helper f (idx + 1) len (Array.push (f (Array.get idx arr)) acc)
  in
    helper f 0 (Array.length arr) Array.empty

It wouldn’t be as fast, but that’s essentially how it works.

I guess one could add some compiler magic for “smarter iteration”, but it would be more complex than what’s there now and I’m not sure it would be worth it.

50

Yes, it would be fairly complex. It would only be worth it if your new data structure were to end up replacing List and Array altogether, such that they were completely removed from Elm. Continuing to support pattern matching and construction on :: and [] would allow existing List based code to be migrated automagically.