haskell - 为什么 Haskell 中的内存函数会消耗如此多的内存？

Question

我写了一段Haskell代码来计算Collatz chain的长度。给定数字 n，如果 n 为偶数，则序列中的下一个数字为 n/2；如果 n 为奇数，则序列中的下一个数字为 3*n+1。当序列收敛到 1 时结束。我想找到从低于某个输入数字的任何数字开始时最长链的长度。

我尝试使用内存函数来实现长度计算，因为我预计需要从某些数字开始的链长度。因此，从 726 开始的链的长度将只是 1 + 从 363 开始的链的长度，这已经被计算出来了。我的代码如下所示。

collatz :: Int -> Int
collatz n
    | even n = n `div` 2
    | otherwise = 3 * n + 1

collatzLength :: Int -> Int
collatzLength = (fmap len [0 ..] !!)
    where len 0 = 0
          len 1 = 1
          len n = 1 + (collatzLength . collatz $ n)

maxLengthBelow :: Int -> Int
maxLengthBelow = foldl1 max . fmap collatzLength . enumFromTo 1

main :: IO()
main = print $ maxLengthBelow 10000

此代码可以工作，但需要大量内存。在对其进行分析时，输入 10000 运行 main，len 仅被调用 21664 次，正如预期的那样，但程序需要 16 秒和 4.5Gb 内存!是什么占用了所有这些内存？我本来期望内存函数能够产生快速、低内存的解决方案。

Answer 1

让 Collat​​z 序列如此有趣的原因之一是，有一些小的起始种子会带你一路进入大气层，一路到达 1。特别是，9663 一路走到 27114424在它崩溃之前——这是一个很长的内存列表!

而且，就其值(value)而言，我希望您的内存列表每个元素使用三个机器字:一个用于 Int 上的 I# 构造函数，一个用于包含数字，一个用于 (:) 构造函数。我们问一下存储27114424个元素需要多少空间，那么:

> 27114424 * (64*3) / 1024 {-Kb-} / 1024 {-Mb-} / 1024 {-Gb-}
4.8484368324279785

所以 4.5Gb 听起来不错，甚至可能有点低。