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?
On Sun, 2008-07-13 at 20:24 +0200, 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]]
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.
That's because you aren't using it.
How to fix?
Use your memoized function.
Logesh Pillay
Why? Its as if memoization is being ignored in the haskell version. How to fix?
Shouldn't the definition of p' call (the memoized) p somewhere? In other words, I can't see any memoization, you seem to just map a normal, expensive, recursive function p' over a list. (Another difference is that Python's associative arrays are likely to be faster than Haskell's linear-time indexed lists.) -k -- If I haven't seen further, it is by standing in the footprints of giants
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
participants (4)
-
Derek Elkins -
Henning Thielemann -
Ketil Malde -
Logesh Pillay