Re: Re[2]: [Haskell-cafe] memoization

On Thu, Sep 10, 2009 at 6:34 AM, Peter Verswyvelen wrote:

You might want to watch out for multithreading issues, although in this case, I don't think it will cause sever problems, besides a couple of redundant cache updates.

On Thu, Sep 10, 2009 at 2:07 PM, Bulat Ziganshin wrote:

...

Hello staafmeister,

Thursday, September 10, 2009, 3:54:34 PM, you wrote:

...

What do you think about such a function? This function is

a bit of refactoring

-- "global variable" in haskell way cache = unsafePerformIO $ newIORef M.empty

Watch out! This is not necessarily the same. The cache in the original message was one per function, not one globally, because the let occurred inside a lambda binding. However, because the body of cache didn't depend on f, we can use lambda calculus rules to lift the let outside the lambda. So your transformation is completely valid... And yet, the original code works, and Bulat's equivalent code does not (in fact you can make a segfault using it). I wouldn't dare say the original code is "correct" though, since a valid transformation can break it. Compilers do valid transformations. O unsafePerformIO, how I love thee... Luke

...

memo f x = unsafePerformIO$ do                       m <- readIORef cache                       case M.lookup x m of                         Just y -> return y                         Nothing -> do let res = f x                                       writeIORef cache $ M.insert x res m                                       return res

memo2 = curry . memo . uncurry

-- Best regards,  Bulat                            mailto:Bulat.Ziganshin@gmail.com

_______________________________________________ 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