Tired of being limited to 8 arguments with Html.Lazy? Then please take a look.
11 Likes
I have turned this into an proposal in elm/html.
5 Likes
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
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).
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.
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.
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
In my mind there seems to me a confusion between some concepts going on there.
- 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.
- Memoization is caching the results of a pure function to avoid recomputing it.
- 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
It would be useful for Advent of Code at least!
I think this is a great summary of the three distinct meanings of âlazyâ.
Iâm not sure they are entirely orthogonal, in particular number 1. is most useful if you have binary decision as to whether or not to compute the value. But, for the most part, lazy evaluation is helpful in the cases that whether or not a value gets computed is âcomplexâ. This likely means that if you âjust use thunksâ youâll end up with situations in which you compute the thunk more than once.
Lazy evaluation at the language level means that you compute a value at most once. If you implement this yourself in an eager language by simply using a thunk, the danger is that you will sometimes compute the value more than once. But if you add â2. Memoizationâ together with â1. Lazy evaluationâ then you kind of get the best of both worlds, in that the expensive computation is computed at most once.
I realise @gampleman knows all this, and his suggestion regarding a library where the computed result is stored on the function object, is essentially adding lazy computation to an eager language (and would have to be done as a privileged library). I think there are some papers regarding this, for example adding lazy evaluation to Oâcaml, and there is an interesting paper on Wadler: Language design " How to add laziness to a strict language, without even being odd"
1 Like