[Haskell-cafe] memoization

[Ryan Ingram]

On Thu, Sep 10, 2009 at 5:46 PM, Luke Palmer <lrpalmer at gmail.com> wrote:
> 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...

Right, which is why you should write it like this:

memoIO :: Ord a => (a -> b) -> IO (a -> IO b)
memoIO f = do
   cache <- newIORef M.empty
   return $ \x -> 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

memo :: Ord a => (a -> b) -> (a -> b)
memo f = unsafePerformIO $ do
    fmemo <- memoIO f
    return (unsafePerformIO . fmemo)

I don't think there is any valid transformation that breaks this, since the
compiler can't lift anything through unsafePerformIO.  Am I mistaken?

  -- ryan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090910/68e285f5/attachment.html