学习Haskell:看似循环的程序 - 请帮助解释

Question

我现在正在阅读Doets和Van Eijck撰写的"The Haskell Road to Logic,Math,and Programming"一书.在本书之前,我从未接触过任何函数式编程语言,因此请记住这一点.

在本书的早期,它还提供了以下用于素性测试的代码:

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调用primes1,素数列表.这是"懒惰列表"的第一个例证.该列表被称为"懒惰",因为我们只计算列表中进一步处理所需的部分.为了定义primes1,我们需要对素数进行测试,但该测试本身是根据函数LD定义的,而函数LD又是指primes1.我们似乎在一圈跑来跑去.通过避免2的素数测试,可以使这个圆圈成为非恶意.如果给出2是素数,那么我们可以在LD检查中使用2的素数3是素数,依此类推,我们就可以了并运行

虽然我认为我理解这个解释,但如果有人能用非专业人士的说法解释,我将不胜感激:

1. 什么是"懒惰列表"以及它在这种情况下如何应用？
2. 如何知道2是素数可以让程序变得非恶性？

任何答案都非常感谢.

Answer 1

首先要注意的是,它本身就没有任何代码.它只是一堆数学表达式,在我们尝试从它们中提取一些值之前,它是多么循环并不重要.我们怎么做？

我们可以这样做:

print $ take 1 primes1

这里没问题.我们可以在不查看任何递归代码的情况下获取primes1的第一个值,它明确地显示为2.如何:

print $ take 3 primes1

让我们尝试扩展primes1以获得一些价值.为了保持这些表达式的可管理性,我现在忽略了这些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..]

我们使用guard子句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那么扩展那个表达式,我们最终会很快陷入循环.)

Answer 2

为了:

懒惰是仅在您需要时评估表达式的属性,而不是在您可能的时候.懒惰列表可能是无限的.显然,如果评估不是懒惰,那么尝试评估无限列表将是一个坏主意.

我不确定"非恶意"意味着什么,但我认为你会发现将值"2"作为已知素数提供了递归的基本情况,即它提供了一个特定的输入,程序将在该输入上终止.编写递归函数(或实际上是一组相互递归函数)通常涉及在连续的应用步骤中减少朝向该基本情况的一些输入值.

作为参考,这种形状的程序片段通常称为相互递归.在这种情况下,术语"循环引用"并不是您真正应用的.