Memoization using `IORef`

Memo.hs

module Memo where

import Data.IORef
import System.IO.Unsafe
import qualified Data.Map as M

memoIO :: (Ord a) => (a -> b) -> IO (a -> IO b)
memoIO f = do
  v <- newIORef M.empty
  return $ \x -> do
    m <- readIORef v
    case M.lookup x m of
      Just r -> return r
      Nothing -> do
        let r = f x
        modifyIORef' v (M.insert x r)
        return r

memo :: (Ord a) => (a -> b) -> (a -> b)
memo f = unsafePerformIO . unsafePerformIO (memoIO f)

fib :: Integer -> Integer
fib = memo go
  where
  go :: Integer -> Integer
  go 0 = 0
  go 1 = 1
  go n = fib (n - 1) + fib (n - 2)

main :: IO ()
main = print $ fib 2000