New subject: Re[2]: memoization

10 Sep 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 
...
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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

Alberto G. Corona

Alberto G. Corona

tags

participants (1)