Is this memoization the right job?

Question

I have been working on Project Euler # 14 solution for a while in Haskell, but for some reason I cannot make it work. I solved the problem using Groovy a while ago, and I think that I am using basically the same method here. However, the program runs incredibly slowly, even just finding the first 10,000 lengths, and I really lost why now. I think I'm using memoization correctly, but I am running out of memory even with small datasets in GHCI.

Here is what I have come up with so far.

collatz = (map collatz' [0..] !!) where collatz' n | n == 1 = 1 | n `mod` 2 == 0 = 1 + collatz (n `div` 2) | otherwise = 1 + collatz (3 * n + 1) 

I would execute map collatz [1..1000000] to get an answer to the problem, but map collatz [1..10000] gives me an error in memory and also takes a few seconds to complete the job.

If anyone could give me some idea what the problem is with this program, that would be great! I tried a lot of things and I just got stuck and need a hand.

Thanks!

Answer 1

Remembering works very well here. In fact, it works so well that it fills all of your memory. The intermediate members of the Collatz sequence become quite large. The largest term that occurs in any sequence, starting from 1 to 1000000 , is the number 2974984576 . So this is the length of the list you are trying to create in memory.

On the other hand, direct execution of the Collatz function without memoization should work fine for this problem.