为什么这个Haskell代码片段不是无限递归的？

Question

为了帮助我学习Haskell,我正在研究Project Euler的问题.在解决了每个问题之后,我会针对Haskell wiki检查我的解决方案,以尝试学习更好的编码实践.下面是解决到问题3:

primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

primeFactors n = factor n primes
  where
    factor n (p:ps) 
        | p*p > n        = [n]
        | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
        | otherwise      = factor n ps

problem_3 = last (primeFactors 317584931803)

我对此的天真解读是根据primes定义primeFactors来定义的primes.所以评估primeFactors 9将遵循这个过程:

1. 评估factor 9 primes.
2. 要求primes它的第一个元素,即2.
3. 要求primes它的下一个元素.
4. 作为此过程的一部分,请进行评估primeFactors 3.
5. 要求primes它的第一个元素,即2.
6. 要求primes它的下一个元素.
7. 作为此过程的一部分,请进行评估primeFactors 3.
8. ...

换句话说,步骤2-4将无限重复.显然我错了,因为算法终止了.我在这里犯了什么错误？

Answer 1

primeFactors只读取它正在评估的数字的平方根.它永远不会在列表中进一步查看,这意味着它永远不会"赶上"它正在测试包含在列表中的数字.因为Haskell很懒,这意味着primeFactors测试会终止.

另一件需要记住的事情是,primes每次访问时都不是一个评估列表的函数,而是一个懒惰构造的列表.因此,一旦访问了第15个元素,第二次访问它是"免费的"(例如,它不需要任何进一步的计算).

Answer 2

凯文的回答令人满意,但请允许我指出你逻辑中的缺陷.这是#6错了.所以我们正在评估primeFactors 3:

primeFactors 3          ==>
factor 3 primes         ==>
factor 3 (2 : THUNK)    ==>
2*2 > 3 == True         ==>
[3]

永远不需要评估THUNK来确定它primeFactor 3是什么[3].

Answer 3

primeFactors 3不会要求primes它的下一个元素,只有第一个元素,因为2*2它比3已经大