Functions as data as functions - a quick memoization hack
Tags: webdev, functional
Published: 2021-01-06 11:25:45

---
title: Functions as data as functions - a quick memoization hack
published: true
description: 
tags: webdev, functionalprogramming
//cover_image: https://direct_url_to_image.jpg
---

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

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

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

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