[Haskell-cafe] memoization

[Henning Thielemann]

On Sun, 13 Jul 2008, Logesh Pillay wrote:

> I know we can perform memoization in Haskell.  The well known recursive 
> Fibonacci example works v. well.  f(10000) returns a virtually instant answer 
> which would not be possible otherwise.
>
> My (probably naive) function to give the number of partitions of a number :-
> p = ((map p' [0 .. ]) !!)
> where
> p' 0 = 1
> p' 1 = 1
> p' n = sum [(((-1) ^ (k+1)) * ( p' (n-((k*(3*k-1)) `div` 2))  +  p' (n-((k*(3*k+1)) `div` 2)))) | k  <- [1 .. n]]

You don't use memoization here - so why do you expect it would take place?

I have a fast implementation:
   http://darcs.haskell.org/htam/src/Combinatorics/Partitions.hs