Here is a generic memoization module in Haskell. There are three
exports. Memoized a b is the type of a memoized function from as
to bs, recall makes a memoized function call, and forget makes a
memoized function call, forgets the memoization table, and gives you
the result.
module Memoize
(Memoized, recall, forget) where
import Data.Map
import Control.Monad.State
type Memoized a b = a -> State (Map a b) b
recall :: Ord a => Memoized a b -> Memoized a b
recall func arg = do
memory <- get
case Data.Map.lookup arg memory of
Nothing -> memorize func arg
Just result -> return result
memorize :: Ord a => Memoized a b -> Memoized a b
memorize func arg = do
result <- func arg
modify (insert arg result)
return result
forget :: Memoized a b -> a -> b
forget func arg = evalState (func arg) emptyAnd it’s use, for our old friend the Fibonacci sequence,
import Memoize
fib :: Int -> Integer
fib = forget memFib
memFib :: Memoized Int Integer
memFib 0 = return 1
memFib 1 = return 1
memFib n = do
x <- recall memFib (n - 1)
y <- recall memFib (n - 2)
return (x + y)
main = putStrLn $ show $ fib 10There are two things lacking with this approach. First, there is no
support for functions of more than one argument (without manually
packing and unpacking them). Second, it exposes the memoization
table. A user of the module could use the get and put functions.