haskellmemoizationrepresentable

What is the role of Haskell's evaluation strategy in Memoization via Representable

The article Memoization via Representables does a great job at explaining how to memoize recursive functions via Representables. It starts by implementing the Fibonacci sequence as a fixed point of fibOp:

fibOp :: Num a => (Natural -> a) -> (Natural -> a)
fibOp v 0 = 0
fibOp v 1 = 1
fibOp v n = v (n-1) + v (n-2)

fix f = let x = f x in x

fibNaive :: Num a => Natural -> a
fibNaive = fix fibOp

This implementation is not efficient as it calculates the same values many times.

The article goes on to introduce the mutual inverse functions streamTabulate and streamIndex (which will later be generalised in the Representable type class). These functions allow us to implement a memoized versions of fibNaive:

fibSmart :: Num a => Natural -> a
fibSmart = fix (streamIndex . streamTabulate . fibOp)

And it is at this point where the article gets somewhat "handwavy":

If we compose our tabulation function with fibOp, we get a function turns a function v into a Stream, over which we can index to get back a function. In this case, however, the same stream is shared for all arguments.

What does this mean exactly? Apparently this memoization technique works because of Haskell's lazy evaluation strategy and because it tries not to evaluate expressions "unnecessarily". For example this answer mentions that Haskell computes any given expression at most once per time that its surrounding lambda-expression is entered. The surrounding lambda-expression of streamTabulate however is entered once per iteration induced by the surrounding fix, which would mean streamTabulate is potentially evaluated multiple times.

Why and how does this approach work? Which aspect of Haskell's evaluation strategy does it exploit?

Solution

  • Your function:

    fibSmart :: Num a => Natural -> a
fibSmart = fix (streamIndex . streamTabulate . fibOp)

    can indeed be expanded by inlining (.) to:

    fibSmart = fix (\f -> streamIndex (streamTabulate (fibOp f)))

    but the lambda \f -> ... here is only entered once by the fix function.

    You can also see that by further inlining fix:

    fibSmart = let f = streamIndex (streamTabulate (fibOp f)) in f