haskell - 为什么这个 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

Kevin's answer is satisfactory, but allow me to pinpoint the flaw in your logic. It is #6 that is wrong. So we're evaluating primeFactors 3:

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

The THUNK need never be evaluated to determine that the primeFactor 3 is [3].

Answer 3

primeFactors 3 doesn't ask primes for its next element, only the first one, because 2*2 is greater than 3 already