I'm working on problem 14 of Project Euler (http://projecteuler.net/problem=14). I'm trying to use memoization so that I save the length of the sequence for a given number as a partial result. I'm using Data.MemoCombinators for that. The program below produces a stack overflow.
import qualified Data.MemoCombinators as Memo
sL n = seqLength n 1
seqLength = Memo.integral seqLength'
where seqLength' n sum = if (n == 1) then sum
else if (odd n) then seqLength (3*n+1) (sum+1)
else seqLength (n `div` 2) (sum+1)
p14 = snd $ maximum $ zip (map sL numbers) numbers
where numbers = [1..max]
max = 999999
The stack overflow should be due to sum+1 being evaluated lazily. How can I force it to be evaluated before each call to seqLength? BTW, is memoization well implemented? I'm more interested in pointing out my Haskell mistakes than in solving the exercise.
The most common ways of forcing evaluation are to use seq, $! or a bang pattern. However sum+1 is not the culprit here. maximum is. Replacing it with the stricter foldl1' max fixes the stack overflow error.
That taken care of, it turns out that your memoization here is no good. Memo.integral only memoizes the first argument, so you're memoizing partial applications of seqLength', which doesn't really do anything useful. You should get much better results without tail recursion so that you're memoizing the actual results. Also, as luqui points out, arrayRange should be more efficient here:
seqLength = Memo.arrayRange (1, 1000000) seqLength'
where seqLength' 1 = 1
seqLength' n | odd n = 1 + seqLength (3*n+1)
| otherwise = 1 + seqLength (n `div` 2)