Memoization

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) empty

And 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 10

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

Justin Pombrio

About Me

Code

Serve

Show

Tell

Memoization