Is this memoization working properly?

Question

I'm have been working on solving Project Euler #14 for a while now in Haskell, but for some reason, I'm unable to get it working. I solved the problem using Groovy a while ago, and I think I'm using basically the same method here. However, the program runs incredibly slow even just finding the first 10,000 lengths, and I'm really lost now as to why. I think I'm using memoization right, but I'm running out of memory even with smallish data sets in GHCI.

Here's what I've 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'd be running map collatz [1..1000000] to get the answer to the problem, but map collatz [1..10000] gives me an out of memory error, and also takes a good few seconds to finish running.

If anyone could give me some insights as to what the problem with this program is, that would be great! I've tried a lot of things and I'm just stuck and need a hand.

Thanks!

Answer 1

Memoization is working just fine here. In fact, it's working so well that it fills up all your memory. The intermediate terms of the Collatz sequence are getting quite large. The largest term that occurs in any sequence starting with 1 up to 1000000 is the number 2974984576. So this is the length of the list you are trying to build in memory.

On the other hand, just directly implementing the Collatz function without memoization should work fine for this problem.