Logesh Pillay lpillay at webafrica.org.za
Sun Jul 13 14:24:13 EDT 2008

```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]]

It is an attempt to apply the Euler recurrence formula (no 11 in
http://mathworld.wolfram.com/PartitionFunctionP.html )

It works but it is shockingly slow.  It is orders of magnitude slower
than the Python memoized version which runs very fast.
parts = {0:1, 1:1}
def P(n):
if not n in parts:
parts[n] = sum ([( ((-1) ** (k+1)) * ( P(n-((k*(3*k-1))//2)) +
P(n-((k*(3*k+1))//2)) ) ) for k in xrange (1, n+1)])
return parts[n]

Why?  Its as if memoization is being ignored in the haskell version.
How to fix?

```