[Haskell-cafe] memoization

[Luke Palmer]

On Thu, Sep 10, 2009 at 6:34 AM, Peter Verswyvelen <bugfact at gmail.com> 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
> <bulat.ziganshin at gmail.com> 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 at gmail.com
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>