I assume you already know what memoization is and why we might want to use it.
In the context of reactive computations, memoization can improve performance a great deal, avoiding recalculation of data that has not changed. Most reactive paradigms, however, achieve only some trivial memoization – i.e. only for the last element, and only for functions fully lifted into the reactive model (shallow, not applicable to recursive or inner functions).
I am interested in richer memoization for reactive programming. The trivial example problem for memoization seems to be fibonacci sequence. Consider mapping it across a list of integers:
fib n = if (n < 2) then n else fib (n - 1) + fib (n - 2)
map fib [7,6,5,4,5]
As written, this would be very expensive because we recompute fibonacci values very often – both vertically within each calculation of fib, and horizontally across the list of integers. For example, if we apply `map fib [7,6,5,4,5]` we’ll perform the same computation `fib 2` a total of 21 times, and `fib 3` a total 13 times.
One challenge, then, is to support memoization in both the horizontal and vertical directions.
Haskell developers have found elegant, pure ways to achieve that level of memoization. The common idea is to represent a lazy data structure that maps every element of the domain (potentially infinite) to an element in the range. Computations will slowly complete this data structure.
memoFib = map fib [0,1..] !!
where fib 0 = 0
fib 1 = 1
fib n = memoFib (n - 1) + memoFib (n - 2)
map memoFib [7,6,5,4,5]
This example is borrowed from the Haskell wiki page on memoization. We can do better – generalize, use a faster lookup structures, and separate the structure from the function being memoized. Packages for this include Data.MemoCombinators and Data.MemoTrie. A trie would be preferable to a simple infinite list because it better supports sparse computations and fast lookups.
Unfortunately, growing an infinite data structure in a long-running program causes very predictable problems – space leaks, when a particular domain element is never encountered again. For reactive programming, space leaks are unacceptable, and memory consumption should be predictable over time.
I must be able to GC results that haven’t been used recently, while preserving results that have been used recently.
Somehow I need windowed memoization.
For example, instead of memoizing the entire history, I memoize only results for the previous two elements in a list. When I finish mapping fib to the last element of [7,6,5,4,5], I’ve forgotten fib 7 and fib 6. But I’ve still computed fib 5 only once, since it is available within the window at every step.
I’m short on ideas for how to achieve this elegantly, purely, unobtrusively. I expect I could hack a decent unobtrusive solution with unsafePerformIO and state, if I’m careful about interactions with data-parallelism and anticipation. I might be able to create an obtrusive solution with a stateful memoization monad. If I don’t mind shallow memoization, I could probably lift explicit use of state right into the reactive model.