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!
Top comments (0)