Haskell，memoization，栈溢出

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之前强制对其求值？顺便说一句，memoization实现得好吗？我更感兴趣的是指出我的Haskell错误，而不是解决这个练习。

Answer 1

强制求值的最常见方法是使用seq、$!或bang模式。然而，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)

Answer 2

我不熟悉Data.MemoCombinators，所以一般的建议是:尝试seqLength (3*n+1) $! (sum+1) (当然，即使是n也是如此)。

Answer 3

当我们可以利用懒惰时，为什么还要使用MemoCombinators呢？诀窍是做一些像这样的事情

seqLength x = lengths !! x - 1
   where lengths = map g [1..9999999]
         g n | odd n = 1 + seqLength (3 * n + 1)
             | otherwise = 1 + seqLength (n `div` 2)

它应该以一种记忆的方式工作。由@hammar改编自非尾递归解决方案

当然，对于记忆的情况，seqLength是O(n)，因此它的性能较差。然而，这是可以补救的！我们简单地利用了Data.Vector是流式传输的并且具有O(1)随机访问的事实。fromList和映射将同时完成(因为映射将简单地生成块，而不是实际值，因为我们使用的是盒式向量)。我们也会使用非记忆版本，因为我们不可能记住每一个可能的值。

import qualified Data.Vector as V

seqLength x | x < 10000000 = lengths V.! x - 1
            | odd x = 1 + seqLength (3 * n + 1)
            | otherwise = 1 + seqLength (n `div` 2)
   where lengths = V.map g $ V.fromList [1..99999999]
         g n | odd n = 1 + seqLength (3 * n + 1)
             | otherwise = 1 + seqLength (n `div` 2)

它应该与使用MemoCombinators相媲美或更好。不要在这台计算机上安装haskell，但是如果你想知道哪一个更好，有一个叫做Criterion的库，它非常适合做这类事情。

我认为使用Unboxed Vectors实际上可以提供更好的性能。当你评估一个项目(我认为)时，它会迫使所有东西都立即生效，但无论如何你都需要这样做。因此，您可以只运行一个foldl' max来获得一个应该具有较少恒定开销的O(n)解决方案。