Re[Haskell-cafe] [2]: memoization

[mf-hcafe-15c311f0c at etc-network.de]

On Thu, Sep 10, 2009 at 05:23:26AM -0700, staafmeister wrote:
> To: haskell-cafe at haskell.org
> From: staafmeister <g.c.stavenga at uu.nl>
> 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