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

为了帮助我学习Haskell，我正在解决Project Euler上的问题。解决了每个问题后，我检查了我的解决方案与Haskell wiki，试图学习更好的编码实践。这里是the solution到problem 3：为什么这个Haskell代码片段不是无限递归的？

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。
询问primes为其第一个元素，即2.
询问primes的下一个元素。
作为此过程的一部分，请评估primeFactors 3。
询问primes为其第一个元素，即2.
询问primes的下一个元素。
作为此过程的一部分，请评估primeFactors 3。
...

换句话说，步骤2-4将重复无限。很明显，我错了，算法终止。我在这里犯了什么错误？

来源

2011-12-12 Matthew Pirocchi

因为，如这里的答案说，'直到素的平方超过被测试的数目primeFactors'只访问'primes'，该代码相当于'素数= 2：[N |所有（（> 0）.rem n）$ takeWhile（（<= n）。（^ 2））素数]这显然是非循环的。 –

primeFactors永远只能最多读取它的评估数的平方根。它从来没有在列表中看得更远，这意味着它永远不会“追上”它正在测试列入列表中的数字。由于Haskell是懒惰的，这意味着primeFactors测试确实终止。

还有一点要记住的是，primes不是每次访问它时都会评估列表的函数，而是一个懒惰地构建的列表。因此，一旦第15个元素被访问过一次，第二次访问它就是“免费”的（例如，它不需要任何进一步的计算）。

来源

2011-12-12 03:17:30

细节：访问它第二次还是费15个dereferencings，因为我们正在做的利弊小区列表...这可能是很多，如果你有上百个列表元素 – naiad

@sparkleshy这将是（约）'开方二次的（N ）'，即将（近似）线性成本添加到*上述线性*计算中。 –

primeFactors 3不问primes它的下一个元素，只有第一个，因为2*2大于3已经

来源

2011-12-12 05:59:01 asvyazin

凯文的答案是令人满意的，但让我找出这个安全漏洞存在的逻辑。＃6是错的。因此，我们正在评估primeFactors 3：

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

的THUNK永远不需要进行评估，以确定primeFactor 3是[3]。

来源

2011-12-12 22:17:28

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

回答

相关问题