On Jan 12, 2008 11:30 PM, David Benbennick <[EMAIL PROTECTED]> wrote: > On 1/12/08, Henning Thielemann <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe