A faster `List.map` for Elm

Show and Tell
3

This is a neat optimization! I think the most generic version I have heard of is to do this for any direct use of a constructor. For example:

type Pairs = Nil | Cons Int Int Pairs

swap : Pairs -> Pairs
swap pairs =
  case pairs of
    Nil         -> Nil
    Cons x y ps -> Cons y x (swap ps)

Should be able to do this optimization in that case as well. And any other “list-like” constructor. I think any constructor should work to some extent though. For example:

type Tree = Empty | Node Int Tree Tree

double : Tree -> Tree
double tree =
  case tree of
    Empty      -> Empty
    Node n l r -> Node (2 * n) (double l) (double r)

I think it’d be possible to figure out some variation that’d partially handle this kind of scenario. Like recursing normally on r and doing some sort of trick for l. I am sure I have read something about this before, but I cannot remember now! Maybe in OCaml or SML? I think there are additional techniques that can handle even more cases (like mutually recursive types and functions) but I am drawing a blank on what terms to search for. If someone can find the papers on “generalizing tail recursion” or whatever, please share them!

Anyway, I would be curious the effect this has on speed/locality of allocating data structures. Maybe things end up in a nicer order in the heap, but I would want to see a breakdown.

Would be really cool to explore in elm-optimize-level-2 for now I think. Probably combines in interesting ways with deforestation as well!

7 Likes