Beyond Html.Lazy's argument limit

Show and Tell
1

Tired of being limited to 8 arguments with Html.Lazy? Then please take a look.

11 Likes
2

I have turned this into an proposal in elm/html.

5 Likes
3

One thing I don’t quite understand is why is lazy tied to elm/html? Shouldn’t there be a general memoization primitive?

1 Like
4

Wow! That’s an exciting thought.

Maybe like this:

memoize ({ a | lazyDummy : () } -> b) -> { a | lazyDummy : () } -> b
memoize f record =
    f record

The implementation of that function would be replaced with something like:

var _cache = new Map();
var memoize = F2(function(f, record)
  {
    var lastKey;
    var fCache = _cache.get(f);
    var cache = fCache;
    var hasCache = true;
    if (cache === undefined)
    {
      hasCache = false;
    }
    else
    {
      for (var key in record)
      {
        lastKey = key;
        cache = cache.get(record[key]);
        if (cache === undefined)
        {
          hasCache = false;
          break;
        }
      }
    }
    if (hasCache)
    {
      return cache;
    }
    
    var result = f(record);

    var parent = fCache;
    if (fCache === undefined)
    {
        parent = new Map();
        _cache.set(f, parent);
    }
    for (key in record)
    {
      var value = record[key];
      var cache = parent.get(value);
      if (cache === undefined)
      {
        cache = key === lastKey ? result : new Map();
        parent.set(value, cache);
      }
      parent = cache;
    }

    return result;
  });

Note: I wrote this code right now and I haven’t tested it.

Also note that the code uses Map, which none of Elm’s current JS does (but should be fine IMO).

5

This might be a better implementation:

var _cache = new Map();
var memoize = F2(function(f, record)
  {
    var prev = f;
    var parent = _cache;
    for (var key in record)
    {
      var value = record[key];
      var cache = parent.get(prev);
      if (cache === undefined)
      {
        cache = new Map();
        parent.set(prev, cache);
      }
      prev = value;
      parent = cache;
    }
    
    var ret = parent.get(prev);

    if (ret !== undefined)
    {
      return ret;
    }
    
    ret = f(record);
    parent.set(prev, ret);
    return ret;
  });

Edit: Will this leak memory over time? I only add to the map, never remove from it.

6

You’d probably want a library with different options. Html.Lazy is a LRU-1 cache strategy afaict, but in general memoization allows you to trade memory for CPU, and exactly which caching strategy you choose will dictate how that trade will go.

But even having a LRU-1 general purpose memoization would be pretty helpful for performance work in Elm.

7

There was a general memoization primitive in Elm 0.18 with GitHub - elm-lang/lazy: Lazy Evaluation in Elm, but it’s not available in Elm 0.19 mostly because of memory leak concerns as far as I understand it. You can probably use some inspiration from here if you’d like to explore this (especially if you’d like to stick to ES5, Map and WeakMap came later).

I’m sure there are cases where this could be looked into again, but this is not the way that lazy/caching works in Elm. I’m in the process of writing an explainer article about it (hopefully getting it out today or at least before the end of the weekend).

But in a rough summary, the result of the previous lazy computation is stored in the virtual DOM itself, and is re-covered (on cache hits) when diffing the old and new virtual DOMs. This has the nice property that it’s fast and there is no memory leak.

Because of this, Html.Lazy is indeed tied to elm/html / elm/virtual-dom.

2 Likes
8

In my mind there seems to me a confusion between some concepts going on there.

  1. Lazy evaluation is the practice of deferring computing a value until it is actually needed (usually for an effect). As the README there says, this is perfectly possible by just using thunks.
  2. Memoization is caching the results of a pure function to avoid recomputing it.
  3. Sharing (or persistent data structures) is when multiple ways to access a value all share a reference to the same underlying memory.

These are all completely orthogonal. The elm-lang/lazy library seems to mix these up in a particular way that both seems not super useful and introduces various problems of its own. In comparison the Html.Lazy library really does just memoization, but with the special sauce of having a caching strategy where cache hits depend on the position in the DOM tree (and the not insignificant limitation that your memoized function needs to return the Html type).

So what I’m wondering is simply if there is space for a library with pretty much the same design as Html.Lazy, but where a) the return type is a and b) the results are stored on the function object itself (which also means that we don’t need to worry about == the functions).

2 Likes
9

It would be useful for Advent of Code at least!