Haskell、内存、堆栈溢出

Question

我正在研究 Project Euler (http://projecteuler.net/problem=14) 的第 14 题。我正在尝试使用内存功能，以便将给定数字的序列长度保存为部分结果。我正在使用 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、$! 或 bang 模式。然而 sum+1 并不是这里的罪魁祸首。 最大值是。将其替换为更严格的 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)