How do you make a generic memoize function in Haskell?

Question

I've seen the other post about this, but is there a clean way of doing this in Haskell?

As a 2nd part, can it also be done without making the function monadic?

Answer 1

The package data-memocombinators on hackage provides lots of reusable memoization routines. The basic idea is:

type Memo a = forall r. (a -> r) -> (a -> r) 

I.e. it can memoize any function from a. The module then provides some primitives (like unit :: Memo () and integral :: Memo Int), and combinators for building more complex memo tables (like pair :: Memo a -> Memo b -> Memo (a,b) and list :: Memo a -> Memo [a]).

Answer 2

You can modify Jonathan´s solution with unsafePerformIO to create a "pure" memoizing version of your function.

import qualified Data.Map as Map import Data.IORef import System.IO.Unsafe  memoize :: Ord a => (a -> b) -> (a -> b) memoize f = unsafePerformIO $ do      r <- newIORef Map.empty     return $ \ x -> unsafePerformIO $ do          m <- readIORef r         case Map.lookup x m of             Just y  -> return y             Nothing -> do                      let y = f x                     writeIORef r (Map.insert x y m)                     return y 

This will work with recursive functions:

fib :: Int -> Integer fib 0 = 1 fib 1 = 1 fib n = fib_memo (n-1) + fib_memo (n-2)  fib_memo :: Int -> Integer fib_memo = memoize fib 

Altough this example is a function with one integer parameter, the type of memoize tells us that it can be used with any function that takes a comparable type. If you have a function with more than one parameter just group them in a tuple before applying memoize. F.i.:

f :: String -> [Int] -> Float f ...  f_memo = curry (memoize (uncurry f))