http://hackage.haskell.org/package/stringtable-atom
There are a number of generalized memoization libraries. This one
http://hackage.haskell.org/package/data-memocombinators
doesn't use `unsafePeformIO`, but instead imports the Array package. If you check out
http://hackage.haskell.org/packages/archive/array/0.2.0.0/do...
you will find 696 uses of "unsafe" in one module...
http://hackage.haskell.org/package/MemoTrie
by contrast takes a different approach.
AIUI, it's possible to implement generalized memoization in haskell w/o unsafePerformIO, and both memocombinators and MemTrie do so. I take your point that if necessary, they could have been written to use unsafePerformIO, and as long as the library authors know what they're doing, and are careful, that would be OK.
So, you don't actually need to read CS papers to do memoization in haskell. You just need to know that the libraries that do it have "memo", not "memoize" in their names. This stuff, could, perhaps be easier to find.
memo :: Eq k => (k -> v) -> k -> v
memo f = unsafePerformIO $ do
ref <- newIORef [] :: IO (IORef [(k,v)]) -- make a page for a table
return $ \k -> unsafePerformIO $ do -- when f is applied to k
memotable <- readIORef ref -- get out the table
case lookup k memotable of -- see if k has been done
Just x -> return x -- if it has, we're done!
Nothing -> do -- if it hasn't
let a = f k -- calculate f k
atomicModifyIORef ref $ \t -> ((k,a):t,()) -- add it to the table before
return a -- returning f k
This is someone's brief treatment, which meets most of the definitions people were using. The clojure procedure is more powerful; as far as I can see, getting something similar in Haskell requires a bit more subtlety.