[Haskell-cafe] Why my program runs out of memory?
Daniel Fischer
daniel.is.fischer at web.de
Fri Jun 25 15:25:59 EDT 2010
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. I was wondering where I have a space leak,
> 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)
Oh, and: this list is not complete, e.g. (0, j) doesn't appear in the list
for j > 1, so the algorithm isn't correct.
> 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
More information about the Haskell-Cafe
mailing list