If you read the memo1 function carefully you'll notice that the cache always contains just one pair. It's coincident that just memo-ing one last function application is enough for the SOE examples. You could, for example, make it memo-ing last two or more results.
The reason for this memoization hack in SOE is complicated. Recursively defined signals using switch will have time/space leak if not for the memoization, which itself is complicated that one can't simply use a shared list to achieve it. Hence the hack using unsafe operation. The loss of sharing of function application results is fundementally rooted in the call-by-need evaluation strategy, which, unlike optimal evaluation, doesn't share the reduction of "virtual redex"es. There are a number of ways to get around this problem, and memoization is one of them. By re-structuring the code, or choosing different data structures, one could also avoid such problems. The evolution of FRP into Yampa/Arrow is a good example, where no memoization is needed. We recently wrote a paper about the leak problem. The draft is at http://www.cs.yale.edu/~hl293/download/leak.pdf. Comments are welcome! Regards Paul Liu On 9/24/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > 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 > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
