为什么这个Haskell代码片段不是无限递归的？ [英] Why is this Haskell code snippet not infinitely recursive?

问题描述

为了帮助我学习Haskell，我正在解决Project Euler上的问题。解决了每个问题后，我检查了我的解决方案与Haskell wiki，试图学习更好的编码实践。这里是解决方案 问题3 ：

  primes = 2：filter（（== 1 ）。length。primeFactors）[3,5 ..] 
 
 primeFactors n =因子n素数
其中
因子n（p：ps）
 | p * p> n = [n] 
 | n'mod` p == 0 = p：factor（n`div` p）（p：ps）
 |否则=系数n ps 
 
 problem_3 = last（primeFactors 317584931803）
  

我的天真地阅读这篇文章的是 primes 是根据 primeFactors 来定义的，它由素数。因此，评估 primeFactors 9 会遵循以下过程：
$ b

1. 评估 factor 9 primes 。


2. 询问素数为其第一个元素，即2。 >
   
3. 为其下一个元素询问 primes 。
   
4. 作为此过程的一部分，评估 primeFactors 3 。


5. 询问素数为其第一个元素，即2。 >
   
6. 为其下一个元素询问 primes 。
   
7. 作为此过程的一部分，评估 primeFactors 3 。


8. ...





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


解决方案

primeFactors 到它正在评估的数字的平方根。它从来没有在列表中看得更远，这意味着它永远不会追上它正在测试列入列表中的数字。因为Haskell是懒惰的，这意味着 primeFactors 测试不会终止。

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



To help me learn Haskell, I am working through the problems on Project Euler. After solving each problem, I check my solution against the Haskell wiki in an attempt to learn better coding practices. Here is 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)

My naive reading of this is that primes is defined in terms of primeFactors, which is defined in terms of primes. So evaluating primeFactors 9 would follow this process:

1. Evaluate factor 9 primes.
2. Ask primes for its first element, which is 2.
3. Ask primes for its next element.
4. As part of this process, evaluate primeFactors 3.
5. Ask primes for its first element, which is 2.
6. Ask primes for its next element.
7. As part of this process, evaluate primeFactors 3.
8. ...

In other words, steps 2-4 would repeat infinitely. Clearly I am mistaken, as the algorithm terminates. What mistake am I making here?

解决方案

primeFactors only ever reads up to the square root of the number it's evaluating. It never looks further in the list, which means it never "catches up" to the number it's testing for inclusion in the list. Because Haskell is lazy, this means that the primeFactors test does terminate.

The other thing to remember is that primes isn't a function that evaluates to a list each time you access it, but rather a list that's constructed lazily. So once the 15th element has been accessed once, accessing it a second time is "free" (e.g. it doesn't require any further calculation).

这篇关于为什么这个Haskell代码片段不是无限递归的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！