23 ms·
True, that. For some functions, memoization in Haskell is dead easy. Like "fibs", which is generally a poor example function but it illustrates a technique yo
by klodolph 16y ago
True, that. For some functions, memoization in Haskell is dead easy. Like "fibs", which is generally a poor example function but it illustrates a technique you can use for dynamic programming in Haskell that doesn't work in strict languages:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Now, I don't know if this technique works for the function you're interested in. If you want something more general, you can do soemthing like:
memoize :: Ord a => (a -> b) -> IO (a -> b)
memoize f = do
ref <- newIORef Map.empty
return $ \x -> unsafePerformIO $ do
m <- liftM (Map.lookup x) (readIORef ref)
case m of
Just y -> return y
Nothing -> let y = f x
in do modifyIORef ref (M.insert x y)
return y
That's just off the top of my head (probably has syntax errors, never mind the type checker), and it has a number of drawbacks. For one, the map will get larger and larger -- you could use a LRU purging scheme but that's more work than I'm doing today. It doesn't support polymorphic functions, this could be fixed with some extra care but because of the way "memoize" would have to work you'll need to know a decent amount about the Haskell type system.
There, I responded to llimllib's ultimatum that somehow my conclusion was incorrect if I didn't personally know how to implement a memoization function. Can I have a cookie?
That rant at the end of my post above was me venting frustrations, on a lot of Haskell forums I see people posting about how much they think Haskell is not the language for them and I think, "If it's not for you, can you go to a forum that's not about Haskell?"