[Haskell-cafe] memoization
Henning Thielemann
lemming at henning-thielemann.de
Sun Jul 13 14:46:40 EDT 2008
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
More information about the Haskell-Cafe
mailing list