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

Question

为了帮助我学习Haskell，我正在解决Euler项目的问题。在解决了每个问题之后，为了学习更好的编码实践，我在Haskell wiki上检查我的解决方案。这里是the solution to problem 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将遵循以下过程：

factor 9 primes.

• Ask

• 为其第一个元素(即2.

• Ask primes为其下一个元素)求值。作为该过程的一部分，对其第一个元素(H 222H 123问询d24)计算primes，作为该过程的一部分，H 225H 126作为此过程的一部分，计算primeFactors 3.

1. ...

换句话说，步骤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]

为了确定primeFactor 3是[3]，永远不需要对THUNK进行评估。

Answer 3

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