Haskell,memoization,堆栈溢出

Question

我正在研究Project Euler的问题14(http://projecteuler.net/problem=14).我正在尝试使用memoization,以便将给定数字的序列长度保存为部分结果.我正在使用Data.MemoCombinators.下面的程序产生堆栈溢出.

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

堆栈溢出应该是由于sum+1被懒惰地评估.如何在每次调用之前强制对其进行评估seqLength？顺便说一句,备忘录是否实施得很好？我更有兴趣指出我的Haskell错误,而不是解决这个问题.

Answer 1

强制评估的最常见的方法是使用seq,$!或爆炸模式.然而,sum+1这不是罪魁祸首.maximum是.用更严格的代替它可以foldl1' max修复堆栈溢出错误.

事实证明,你的备忘录并不好.Memo.integral只记得第一个参数,所以你要记住部分应用程序seqLength',它们并没有真正做任何有用的事情.如果没有尾递归,你应该得到更好的结果,这样你才能记住实际的结果.另外,正如luqui所指出的,arrayRange这里应该更有效率:

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)