haskell - 学习 Haskell : Seemingly Circular Program - Please help explain

Question

我目前正在阅读 Doets 和 Van Eijck 所著的《通往逻辑、数学和编程的 Haskell 之路》一书。在这本书之前，我从未接触过任何函数式编程语言，所以请记住这一点。

在本书的早期，它给出了以下素数测试代码:

ldp :: Integer -> Integer
ldp n = ldpf primes1 n

ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p 
              | p^2 > n      = n
              | otherwise    = ldpf ps n

primes1 :: [Integer]
primes1 = 2 : filter prime [3..]

prime :: Integer -> Bool
prime n | n < 1     = error "not a positive integer"
        | n == 1    = False 
        | otherwise = ldp n == n

ldp 调用 primes1，调用 prime，再调用 ldp，这似乎是一个循环编程。虽然这本书确实提供了这个作为程序执行和终止原因的解释:

ldp makes a call to primes1, the list of prime numbers. This is a first illustration of a ‘lazy list’. The list is called ‘lazy’ because we compute only the part of the list that we need for further processing. To define primes1 we need a test for primality, but that test is itself defined in terms of the function LD, which in turn refers to primes1. We seem to be running around in a circle. This circle can be made non-vicious by avoiding the primality test for 2. If it is given that 2 is prime, then we can use the primality of 2 in the LD check that 3 is prime, and so on, and we are up and running

虽然我认为我理解这个解释，但如果有人能用外行的话解释一下，我将不胜感激:

1. What a "lazy list" is and how it applies in this context?
2. How knowing that 2 is prime allows the program to be non-vicious?

非常感谢任何答案。

Answer 1

首先要注意的是，代码本身什么也不做。它只是一堆数学表达式，在我们尝试从中提取一些值之前，它的循环程度并不重要。我们如何做到这一点？

我们可以这样做:

print $ take 1 primes1

这里没有问题。我们可以在不查看任何递归代码的情况下获取 primes1 的第一个值，它明确地作为 2 存在。那么:

print $ take 3 primes1

让我们尝试扩展primes1得到一些值(value)。为了保留这些
表达式可管理，我现在忽略 print和 take部分，但是
请记住，我们只是因为他们才做这项工作。 primes1是:

primes1 = 2 : filter prime [3..]

我们有我们的第一个值，我们第二个的第一步是扩展过滤器。
如果这是一种严格的语言，我们将首先尝试扩展 [3..] 并得到
卡住。过滤器的一个可能定义是:

filter f (x:xs) = if f x then x : filter f xs else filter f xs

这使:

primes1 = 2 : if prime 3 then 3 : filter prime [4..] else filter prime [4..]

我们下一步必须弄清楚 prime 3是真还是假，所以让我们
使用我们对 prime 的定义来扩展它, ldp和 ldpf .

primes1 = 2 : if ldp 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : if ldpf primes1 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

现在，事情变得有趣了，primes1 引用自己，而 ldpf 需要第一个值
做它的计算。幸运的是，我们可以轻松获得第一个值。

primes1 = 2 : if ldpf (2 : tail primes) 3 == 3 then 3 : filter prime [4..] else filter prime [4..]

现在，我们在 ldpf 中应用保护子句并找到 2^2 > 3 ，因此 ldpf (2 : tail primes) 3 = 3 .

primes1 = 2 : if 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
primes1 = 2 : 3 : filter prime [4..] 

我们现在有了第二个值。请注意，我们评估的右侧从未变得特别大
而且我们从来不需要很远地遵循递归循环。

primes1 = 2 : 3 : if prime 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldp 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf primes1 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : if ldpf (2 : tail primes1) 4 == 4 then 4 : filter prime [5..] else filter prime [5..]

我们使用保护子句rem 4 2 == 0 ，因此我们在这里得到 2。

primes1 = 2 : 3 : if 2 == 4 then 4 : filter prime [5..] else filter prime [5..]
primes1 = 2 : 3 : filter prime [5..]
primes1 = 2 : 3 : if prime 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldp 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf primes1 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (2 : tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

没有守卫匹配，所以我们递归:

primes1 = 2 : 3 : if ldpf (tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : if ldpf (3 : tail (tail primes)) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]

现在3^2 > 5所以这个表达式是 5。

primes1 = 2 : 3 : if 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
primes1 = 2 : 3 : 5 : filter prime [6..]

我们只需要三个值，因此评估可以停止。

所以，现在来回答你的问题。惰性列表是只需要我们评估所需内容的列表，并且
2 有帮助，因为它确保当我们到达递归步骤时，我们总是已经有足够的值
计算出来的。 (想象一下，如果我们不知道 2，扩展这个表达式，我们最终会陷入一个循环
迅速地。)