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. 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.

On Sat, 12 Jan 2008, 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

There was a long thread about a sophisticated technique called "blue prints", which allows you to use binary search trees as memoizing structure. http://www.haskell.org/pipermail/haskell-cafe/2006-September/018204.html

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

Henning Thielemann writes:

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. One should add this most simple case to the Wiki.

A posteriori thought, when I reread that... This is a =part= of the story. Whatever you do with the initial calls, if there is no automatic memoization, further calls will be executed normally. The user has to replace his/her calls with the elements of the memo-array. Suppose (sorry for the awful Fibonacci again...) we define fibs = [fib n | n<-[0 ..]] fib 0 = 0 fib 1 = 1 fib n = fib(n-1) + fib(n-2) If you try to get fibs!!1000 you will die before anyway. The solution is obviously to replace the recursive definition of fib by fib n = fibs!!(n-1) + fibs!!(n-2) This works well. I had a similar problem in physics, perturbation theory offers often some quite intricate, knotty recurrencies, and the memoization offers a solution for the worse than exponential complexity. But I had to use trees, 2_dim lists of lists, etc. in order to sort the order of the creation of the results appropriately. So, I agree wholeheartly with the statement that memoization is not a blind automaton, it should be used consciously, and adapted to concrete needs. Jerzy Karczmarczuk