I recently got thinking about memoisation in Haskell functions to improve efficiency. Here are my notes -
This means adding memoisation to a function transparently (without changing the function signature).
i.e. write a function - memoise :: (a -> r) -> a -> r
so that all we have to do to memoise a function is - memoised_f = memoise f
This seems like an impossible thing to accomplish. Memoisation by definition requires a table/map in memory from argument to return values.
However by exploiting Lazy evaluation, and Compiler optimisations, we can accomplish this in haskell with relative ease. An example from the Haskell wiki -
Here we use lazy evaluation to build a map. And then exploit an optimisation of Haskell compilers that arguments to functions are only evaluated once. i.e. in this case that makes sure that (map fib [0..]) is only evaluated once.
It's perhaps clearer this way, which makes it clear that fibs is a constant that is only evaluated once -
In general however, it is needed to add some kind of a stateful wrapper over the function to be memoised. IORefs in the IO Monad and State threading in the State Monad can be used for this. I however decided that it would be better to write a function to memoise any "Monadic Value" (m s). I also decided to use StateT Monad Transformer to store the State.
Here's a general solution that can memoise any monadic computation by wrapping it inside a StateT Monad Transformer -
Rather than explain how it works, here's an example of using it -
Works as advertised I'd say....