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:[EMAIL PROTECTED] 
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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to