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

[jerzy.karczmarczuk at info.unicaen.fr]

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