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!