I don't know, "me newbie, you expert" ;-) I just pasted the code from the SOE website. But note that it is using pointers to the infinite lists to avoid comparing them by content (which wouldn't work, since they're infinite), so it has to use unsafePerformIO no? inCache :: a -> [(a,b)] -> Maybe b x `inCache` [] = Nothing x `inCache` ((x',y'):xys) = if unsafePtrEq x x' then Just y' else x `inCache` xys But what I don't understand is that I guess this code memoizes the full list, while it should just memoize the tail that is still reachable through the garbage collector? Or maybe that is what a "pointer to list" is? Some kind of weak pointer / stable name that points to the tail of the list that is still needed for evaluation? Hard stuff for a newbie, but I got to understand how it works, so I can fit one more piece of the growing Haskell puzzle :) Peter -----Original Message----- From: Henning Thielemann [mailto:lemming@henning-thielemann.de] Sent: Monday, September 24, 2007 1:44 PM To: Peter Verswyvelen Cc: Haskell-Cafe Subject: Re: [Haskell-cafe] Troubles understanding memoization in SOE On Sat, 22 Sep 2007, Peter Verswyvelen wrote:
Hi,
in SOE, the following memoization function is implemented:
memo1 :: (a->b) -> (a->b) memo1 f = unsafePerformIO $ do cache <- newIORef [] return $ \x -> unsafePerformIO $ do vals <- readIORef cache case x `inCache` vals of Nothing -> do let y = f x writeIORef cache [(x,y)] -- ((x,y) : -- if null vals then [] else [head vals]) return y Just y -> do return y
Hm, why the unsafePerformIO hacks? It should be possible without: http://www.haskell.org/haskellwiki/Memoization