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? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Logesh Pillay-3
Logesh Pillay <[hidden email]> writes:
> 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Logesh Pillay-3
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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |