gistfile1.hs

-- http://atnd.org/events/46727
-- https://gist.github.com/cojna/0918920c7a246961227b

import Control.Monad.State
import qualified Data.Map as M

type Memo = M.Map Int Integer

add :: Int -> Integer -> State Memo ()
add k v = do s <- get
             put (M.insert k v s)

memo :: (Int -> State Memo Integer) -> Int -> State Memo Integer
memo f n = do s <- get
              case M.lookup n s of
                Just v -> return v
                Nothing ->
                  do v <- f n
                     add n v
                     return v

fib :: Int -> State Memo Integer
fib 0 = return 1
fib 1 = return 1
fib n = do x <- memo fib (n-1)
           y <- memo fib (n-2)
           return (x + y)

main = print $ runState (fib 100) M.empty