haskell - 为什么这个 Haskell 表达式这么慢？

Question

我正在研究 Project Euler Problem 14。这是我的解决方案。

import Data.List

collatzLength :: Int->Int
collatzLength 1 = 1
collatzLength n | odd n = 1 + collatzLength (3 * n + 1)
                | even n = 1 + collatzLength (n `quot` 2)

maxTuple :: (Int, Int)->(Int, Int)->Ordering
maxTuple (x1, x2) (y1, y2)  | x1 > y1 = GT
                | x1 < y1 = LT
                | otherwise = EQ

我正在运行以下 GHCi

maximumBy maxTuple [(collatzLength x, x) | x <- [1..1000000]]

我知道，如果 Haskell 严格评估，那么这个时间将类似于 O(n3)。不过，由于 Haskell 的评估是惰性的，看起来这应该是 n 的某个常数倍数。这已经运行了将近一个小时。显得非常不合理。有谁知道为什么？

Answer 1

您假设 collatzLength函数将被内存。 Haskell 不做自动内存。你需要自己做。这是一个使用 data-memocombinators 的示例包裹。

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Integer -> Integer
collatzLength = Memo.arrayRange (1,1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]]

使用 -O2 编译时运行大约 1 秒。 .