[Haskell-cafe] Why my program runs out of memory?

[Daniel Fischer]

On Friday 25 June 2010 20:51:44, Vladimir Ch. wrote:
> I'm trying to solve this problem:
> http://projecteuler.net/index.php?section=problems&id=44, and my
> program runs out of memory.

Compile with optimisations. With -O2, after adding fairly naive isSquare 
and sqrti functions, it seems to run in constant memory (but very slowly, 
you need a better algorithm, really 8-) )

> I was wondering where I have a space leak,

Profiling would tell you where the memory goes.

> I thought that this program doesn't accumulate any data structures
> (i.e. should use constant memory):
>
> CODE BEGINS
>
> -- returns list of pairs (i, j) of indices, for which differences (gen
> j - gen i)
> -- increase, provided that gen has the following property:
> -- gen (i+1) - gen i > gen i - gen (i - 1)
> incDiffPairs gen = iterate next (0, 1)
>                    where next (i, j) = if (i == 0) || gen (j+1) - gen
> j < gen j - gen (i - 1)
>                                           then (j, j + 1)
>                                           else (i - 1, j)
>
> -- returns ith pentagonal number
> pentagonal i = let n = i + 1
>                in n * (3 * n - 1) `div` 2
>
> -- tests if a number is pentagonal
> isPentagonal x = let d = 24 * x + 1
>                  in isSquare d && (1 + sqrti d) `mod` 6 == 0
>
> result44 = head [(pentagonal j - pentagonal i, (i, j)) | (i, j) <-
> incDiffPairs pentagonal,
>                  isPentagonal (pentagonal j - pentagonal i),
>                  isPentagonal (pentagonal j + pentagonal i)]
>
> CODE ENDS