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 -
-- The naive fibonacci functionfib::Int->Integerfib0=1fib1=1fibn=fib(n-1)+fib(n-2)-- Fast memoised fibonacci functionmemoised_fib::Int->Integermemoised_fibx=(mapfib[0..])!!x
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 -
-- Mapping from Indices to Fibonacci numbersfibs::[Integer]fibs=mapfib[0..]-- Fast memoised fibonacci functionmemoised_fib::Int->Integermemoised_fibx=fibs!!x
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 -
moduleMainwhereimportqualifiedData.MapasM(Map,empty,insert,lookup)import"monads-fd" Control.Monad.Trans(lift)import Control.Monad.Trans.State.Lazy(StateT(..))-- Memoise arbitrary monadic computations by wrapping them inside a StateT Monad TransformermemoState :: (Ord k, Monad m) => (k -> m s) -> k -> StateT (M.Map k s) m smemoState f k = StateT $ \s ->caseM.lookupksofNothing->doz<-fkreturn(z,M.insertkzs)Justz->return(z,s)
Rather than explain how it works, here's an example of using it -
-- Our base monadic computation (IO)f::Int->IOStringfx=doputStr"Get Value #"putStrLn$showxputStr"writesomething>"s<-getLinereturns-- Here's the IO monadic value (f) used in a memoised context-- First we wrap f inside StateT using memoState-- Then we chain it together using the usual monadic operations-- Note the use of Lift to perform actions in the IO monadfchain::StateT(StatIntString)IOStringfchain=dos<-f'0lift$putStrLnss<-f'1lift$putStrLnss<-f'0lift$putStrLnss<-f'1lift$putStrLnss<-f'2lift$putStrLnsreturnswheref'=memoStatef-- The memoised computation fchain can now be run as a whole-- Thanks to memoisation, inspite of us invoking (f' 0) and (f' 1) twice, the user will be asked for their values only once.main::IO()main=runStateTfchain$M.empty