13 Jul
2008
13 Jul
'08
2:46 p.m.
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