DEV Community

Mike Solomon
Mike Solomon

Posted on

Functions as data as functions - a quick memoization hack

#webdev #functional

Functional Reactive Programming often requires calculating a current value at time t based on a previous value at time t - 1 all the way back to 0. However, what if that previous value is a function? Let's "unroll" time to see what that would look like. Our functions will be from FizzBang to Number.

data FizzBang = Fizz | Bang initialValue v = case v of Fizz -> 1.0 Bang -> 0.0 valueAt1 v = initialValue v + case v of Fizz -> 3.0 Bang -> 1.0 valueAt2 v = valueAt1 v + 1.0 valueAt3 v = valueAt2 v + case v of Fizz -> 0.0 Bang -> 3.0 currentValue v = valueAt3 v + 6.3
Enter fullscreen mode Exit fullscreen mode

As time goes on, the function call stack gets pretty deep. currentValue has to call four functions: valueAt3, valueAt2, valueAt1 and initialValue to get the current value.

It would be nicer if we could store the values from a previous timestamp so that we did not have to constantly recompute them. But how can we do this? One solution is to use a closure that forces early evaluation of the function:

data FizzBang = Fizz | Bang memoize :: (FizzBang -> Number) -> (FizzBang -> Number) -> FizzBang -> Number memoize f g = let fizz = f Fizz bang = f Bang in \v -> case v of Fizz -> fizz + g Fizz Bang -> bang + g Bang initialValue v = case v of Fizz -> 1.0 Bang -> 0.0 valueAt1 = memoize initialValue (case _ of Fizz -> 3.0 Bang -> 1.0) valueAt2 = memoize valueAt1 (const 1.0) valueAt3 = memoize valueAt2 (case _ of Fizz -> 0.0 Bang -> 3.0) currentValue = memoize valueAt3 (const 6.3)
Enter fullscreen mode Exit fullscreen mode

That solves the function call problem, but it is not very extensible. Every time we want to memoize a function, we have to create all of those let statements and additional closures.

One strategy that I've used recently in PureScript is to abstract memoization using a natural transformation from functions to records.

data FizzBang = Fizz | Bang newtype FizzBang' a = FizzBang' { fizz :: a , bang :: a } class Memoizable f g | f -> g, g -> f where memoize :: Function f ~> g functionize :: g ~> Function f instance memoizableFizzBang :: Memoizable FizzBang FizzBang' where memoize f = FizzBang' { fizz: f Fizz , bang: f Bang } functionize (FizzBang' { fizz }) Fizz = fizz functionize (FizzBang' { bang }) Bang = bang eval = functionize <<< memoize initialValue v = case v of Fizz -> 1.0 Bang -> 0.0 initialValue' = eval initialValue valueAt1 v = initialValue' v + (case v of Fizz -> 3.0 Bang -> 1.0) valueAt1' = eval valueAt1 valueAt2 v = valueAt1' v + 1.0 valueAt2' = eval valueAt2 valueAt3 v = valueAt2' v + (case v of Fizz -> 0.0 Bang -> 3.0) valueAt3' = eval valueAt3 currentValue v = valueAt3' v + 6.3
Enter fullscreen mode Exit fullscreen mode

This has the advantage of keeping something closer to the original functional syntax while staying extensible through the use of type classes. I hope others find it useful as well!

Top comments (0)