相关疑难解决方法(0)

我正在研究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(n ³).由于Haskell懒惰地评估,看起来这应该是n的一些常数倍.这已经运行了近一个小时了.似乎很不合理.有谁知道为什么？

我编译了这个程序,并试图运行它.

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

collatzLength :: Int -> Int
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 $ maximumBy (comparing fst) $ [(collatzLength n, n) | n <- [1..1000000]]

我从GHC获得以下内容

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it. …