Re: [Haskell-cafe] [newbie question] Memoization automatic in Haskell?

12 Jan 2008

      On Jan 12, 2008 11:30 PM, David Benbennick  wrote:
...
On 1/12/08, Henning Thielemann  wrote:
...
Caching is not the default, but you can easily code this by yourself:
Define an array and initialize it with all function values. Because of
lazy evaluation the function values are computed only when they are
requested and then they persist in the array.
But how can I implement memoization for a more complicated function?
For example, perhaps I want to memoize
f :: String -> Int -> Double -> String -> Bool
In Python, it's pretty easy to memoize this.  How can I do it in
Haskell?  I suspect the only way would involve changing the function
signature to use IO or ST.
No, that is one way to do it, and probably the easiest to think about.
 Because its
conceptually pure, I wouldn't be opposed to wrapping it in unsafePerformIO (but
that can be, well, unsafe if you do it wrong :-)

But there is a way to do it if you demand to be a purist, but only if you can
code a data structure representing all values of a type.  Doing this for a
particular type is one of my favorite ways to spend a half hour when
I'm bored :-)

For an obvious case, but to illustrate the point, I'll do Bool.

  data BoolCache a = BC a a

  bools :: BoolCache Bool
  bools = BC True False

  lookupBool :: BoolCache a -> Bool -> a
  lookupBool (BC t f) True  = t
  lookupBool (BC t f) False = f

  memoBool :: (Bool -> a) -> (Bool -> a)
  memoBool f = lookupBool (fmap f bools)

The pattern is the same for any type.  You can do it for types with infinitely
many members, like Integer, but it's trickier (but it's the same pattern, just
a trickier data structure).  The Integer case is scattered here and
there online.
I haven't found any other cases online, but I've implemented a few.
...
It would be nice if I could just tell the compiler "I command you to
memoize this function", and have it produce the required code
automatically.
Tru dat!

But it's not clear what the best way for the compiler writer to do
that is.  For
example, if I know the access patterns of the function, I can design the
aforementioned data structure to favor those.   Also, not every type admits
memoization, for example functions.  But I can certainly envisage a
library providing:

  class Memo a where
    memo :: (a -> b) -> (a -> b)

For a bunch of different types.

Hmm, one probably already exists, actually...

Luke

Re: [Haskell-cafe] [newbie question] Memoization automatic in Haskell?

Luke Palmer