[Haskell-cafe] Troubles understanding memoization in SOE

bf3 at telenet.be bf3 at telenet.be
Mon Sep 24 08:12:25 EDT 2007


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 at 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



More information about the Haskell-Cafe mailing list