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

Alberto G. Corona agocorona at gmail.com
Thu Sep 10 13:14:31 EDT 2009


instead o that you can use  a key such is:
key :: a -> Int
key = unsafePerformIO . hashStableName  . makeStableName

that is defined for any kind of data

then, a unique key for the pair f x could be:

key1 f x=(key f , key x)


However my experience is that ocassionally gives different hashes for the
same object, so maybe a few registers will be duplicated.



2009/9/10 <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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090910/de859d6c/attachment.html


More information about the Haskell-Cafe mailing list