A faster `List.map` for Elm

Show and Tell
6

@evancz you mention allocation and heap layout.
If you were wondering whether there’s just loads of allocations or loads of garbage or something, then no, there isn’t. Just one garbage Cons cell. Otherwise similar to foldl.

Here’s the code:

var $author$project$Main$moduloConsMap = F2(function(f, xs) {
  var tmp = _List_Cons(undefined, _List_Nil);
  var end = tmp;
  while (xs.b) {
    end.b = _List_Cons(f(xs.a), _List_Nil);
    xs = xs.b;
    end = end.b;
  }
  return tmp.b;
});

It pre-allocates a Cons cell (tmp) before starting. This is an extra Cons in front of the list that we’re going to return, so the initial Cons ends up being garbage. We just use it to keep track of the head of the list.

The while loop iterates down the xs list from head to tail, creating a new Cons for the output list at every step. Each step mutates the tail of the previous step. That’s how it avoids having to reverse the list, or iterate over it backwards.

So for every step it’s just allocating a Cons cell plus whatever the function f allocates. That’s why I say it’s like foldl.

The main difference is that the tail of each Cons cell points to a newer Cons cell, rather than an older one. This is the less common direction for pointers to go. v8’s GC will track old-to-new pointers if they cross from one generation to another. But that seems unlikely within one list. Should be easily worth being able to use a while loop!

1 Like