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

On Thu, Sep 10, 2009 at 05:23:26AM -0700, staafmeister wrote:

To: haskell-cafe@haskell.org From: staafmeister Date: Thu, 10 Sep 2009 05:23:26 -0700 (PDT) Subject: Re: Re[Haskell-cafe] [2]: memoization

Hi Bulat,

Bulat Ziganshin-2 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

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

This doesn't work and is exactly what I'm afraid the compiler is going to do. Cache needs to be associated with the function f.

Otherwise one would get conflicts

then make the cache object store functions together with values. cache = unsafePerformIO $ newIORef M.empty memo f x = unsafePerformIO$ do m <- readIORef cache case M.lookup (mkKey f, x) m of Just y -> return y Nothing -> do let res = f x writeIORef cache $ M.insert (mkKey f, x) res m return res memo2 = curry . memo . uncurry This leaves mkKey. Since functions are neither Ord nor Show, you'd have to hack something together yourself. Perhaps an explicit argument to memo? memo :: (Ord a) => String -> (a -> b) -> a -> IO b memo fname f x = unsafePerformIO$ do m <- readIORef cache case M.lookup (fname, x) m of Just y -> return y Nothing -> do let res = f x writeIORef cache $ M.insert (fname, x) res m return res there is probably a better and more elegant solution, but this should at least work. right? matthias