9

我目前正在阅读 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 调用 primes1，即素数列表。这是“惰性列表”的第一个示例。该列表称为“惰性”列表，因为我们只计算列表中需要进一步处理的部分。要定义 primes1，我们需要对素数进行测试，但该测试本身是根据函数 LD 定义的，该函数又引用 primes1。我们似乎在绕圈子跑。通过避免 2 的素数测试，可以使这个循环变得非恶性。如果给定 2 是素数，那么我们可以在 LD 中使用 2 的素数来检查 3 是否为素数，依此类推，我们就成功了并运行

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

  1. 什么是“惰性列表”以及它在这种情况下如何应用？
  2. 知道 2 是素数如何使程序不具有恶意？

非常感谢任何答案。

4

3 回答 3

9

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

我们可以这样做：

print $ take 1 primes1

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

print $ take 3 primes1

让我们尝试扩展primes1以获取一些值。为了使这些表达式易于管理，我现在忽略了printandtake部分，但请记住，我们只是因为它们才进行这项工作。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 和 find 中应用保护子句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，扩展该表达式，我们很快就会陷入循环。）

于 2010-08-18T08:52:01.627 回答
6

为了：

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

我不确定“非恶意”是什么意思，但我认为您会发现将值“2”作为已知素数为递归提供了一个基本情况，即它提供了一个特定的输入，程序将根据该输入终止。编写一个递归函数（或者实际上是一组相互递归的函数）通常涉及在应用的连续步骤中针对这个基本情况减少一些输入值。

作为参考，这种形状的程序片段通常称为相互递归的。在这种情况下，您不会真正应用“循环引用”一词。

于 2010-08-17T19:51:28.637 回答
3

Haskell 的一个决定性特征是它的惰性。列表只是这个故事的一部分。基本上，Haskell 从不执行任何计算，直到：

  1. 需要计算的值来计算其他需要...
  2. 你告诉 Haskell 比其他方法更快地计算一些东西。

因此，该primes1函数会生成一个Integer值列表，但它不会生成满足整体计算所需的任何值。即便如此，如果你这样定义它：

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

你会有问题。primes1将尝试通过（间接）评估来生成其序列中的第一个值prime 2，这将评估ldp 2，这将要求primes1...presto无限循环产生的第一个值！

通过直接返回 2 作为 生成的序列的第一个值primes1，可以避免无限循环。对于序列中生成的每个后续值，primes1已经生成了一个先前值，该值将ldp作为计算后续值的一部分进行评估。

于 2010-08-17T20:06:25.637 回答