## DEV Community is a community of 606,919 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading...

# Functions as data as functions - a quick memoization hack

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
``````

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)
``````

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
``````

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!

## Discussion (0) 