Very interesting, thank you for sharing! I wanted to add a couple notes and ideas that I've had separately.
Syntax I was formerly somewhat keen on having special syntax for other collections. For example, OCaml allows you to say [| 1, 2, 3 |] to create an array. Hassan made a really nice proposal <https://github.com/elm-lang/elm-plans/issues/12> to have it be #[ 1, 2, 3 ] back in 2015. Since then I realized you can do the following: a = Array.fromList s = Set.fromList d = Dict.fromList array = (a[ 1, 2, 3 ]) set = (s[ 1, 2, 3 ]) dict = (d[ 1 => "Tom", 2 => "Sue", 3 => "Jane" ]) (=>) = (,) This is 1 or 2 characters off all the proposals out there, and it is visually much nicer in my opinion. With that knowledge, the case for special syntax seems significantly weaker. I can also imagine detecting when a list is converted to something else and doing something more clever in the compiler. That path seems better overall to me. List performance of map, foldl, and foldr I shared this blog post <https://blogs.janestreet.com/optimizing-list-map/> about optimizing List.map in OCaml a while ago, and Fred did some excellent work on this <https://github.com/elm-lang/core/pull/707>! I have not had a chance to fully assess the impact on generated code size, so I have not merged it in yet. That trick can likely be very helpful for foldl and foldr, but no one has looked into it. I suspect there are many creative things we can do if some focused energy was applied to lists. I have not taken a comprehensive look at this after Elm got TCO, and I suspect we can do better! Alternate Implementations of List Another thing to consider before switching to some other data structure is that we can change the performance profile of List using various techniques behind the scenes. For example: - Skip Lists <https://en.wikipedia.org/wiki/Skip_list> - Finger Trees <https://en.wikipedia.org/wiki/Finger_tree> that maybe do some sort of "compression" on older leaves - I believe there's one that immutable.js does for their lists? Richard told me about something like this. Where "old" nodes grow exponentially in size so the nodes are 1, 2, 4, 8, etc. so it is faster to hop around and you get better locality. Do you recall what this was called Richard? I also think that manually recursing through lists with a case is relatively common, at least in my experience, so I think it'd be good to explore concrete bottlenecks in Elm code and see if there are not creative things we can do to improve the performance profile of List without changing it completely. Anyway, exciting to see your work as always! And hopefully these ideas are helpful! Evan On Monday, June 12, 2017 at 12:15:59 AM UTC+1, Robin Heggelund Hansen wrote: > > I've been doing some thinking on how to improve Arrays in Elm. The result > of that thinking have been written down in this document: > > > https://docs.google.com/document/d/1Z8IC5qk98ISQLP_xKXNOHScCfzkQ8jCVSiYd1SxObB4/edit?usp=sharing > > The document is quite large, but most of it are benchmark results > comparing Arrays and Lists. > > There are some questions at the bottom of the document that I would love > to get feedback on. > -- You received this message because you are subscribed to the Google Groups "Elm Discuss" group. To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
