学习Haskell：看似循环的程序 - 请帮忙解释

Question

我目前正在阅读Doets和Van Eijck的书《Haskell之路：逻辑、数学和编程》，这本书涉及到IT技术。在此之前，我从未接触过任何函数式编程语言，所以请谨记这一点。

在书的早期阶段，它给出了以下用于素数测试的代码：

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，primes1又调用prime，而prime再次调用ldp。虽然书中提供了一种解释来说明程序为什么会执行和终止：

ldp调用质数列表primes1。这是“惰性列表”的第一个例子。该列表被称为“惰性”，因为我们只计算进一步处理所需的列表部分。要定义primes1，我们需要一个测试质数的方法，但是该测试本身是基于函数LD定义的，而LD又引用primes1。我们似乎在循环运行。避免对2进行素性测试可以使这个圆变成非恶性圆。如果假设2是质数，则我们可以在LD检查3是质数时使用2的质数性质，以此类推，程序就可以正常运行。

虽然我认为我理解了这个解释，但如果有人能用通俗易懂的语言解释一下：

1. “惰性列表”是什么，它在这个上下文中如何应用？
2. 知道2是质数如何使程序变得非恶性？

任何答案都将不胜感激。

- Xing

Answer 1

首先需要注意的是，单独看这段代码是没有任何作用的。它只是一些数学表达式的组合，除非我们尝试从中提取一些值，否则它的循环方式并不重要。那么我们该如何提取这些值呢？

我们可以采用以下方式：

print $ take 1 primes1

这里没有问题。我们可以直接获取primes1的第一个值，而不需要查看任何递归代码，因为它明确地表示为2。那么接下来呢：

print $ take 3 primes1

让我们尝试扩展primes1以获取一些值。为了使这些表达式易于管理，我现在忽略了print和take部分，但要记住，我们只是因为它们才做这项工作。 primes1是：

primes1 = 2 : filter prime [3..]

我们有了第一个值，而第二个值的第一步是扩展过滤器。 如果这是一种严格的语言，我们将首先尝试扩展 [3..] 并陷入困境。filter 的一个可能定义如下：

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，想象一下扩展该表达式，我们很快就会陷入循环中。)

- cthulahoops

Answer 2

按顺序：

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

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

供参考，具有此形状的程序片段通常称为相互递归。 在这种情况下，术语“循环引用”并不适用。

- Gian

---

一个恶性循环是指不愉快的事情在人群中传递，例如男孩1欺负男孩2，男孩2告诉他的父亲，父亲生气并对他的员工很严厉，其中一个员工是男孩1的父亲，然后他把自己的挫败感发泄到儿子身上，于是儿子又欺负男孩2... 一个非恶性循环是指不会带来不愉快的循环。 - Matt Ellen

没错，我在其他领域熟悉这个术语，但我从未见过它应用于程序分析。这是一种我不熟悉的 Haskell 术语吗？ - Gian

这不是 Haskell 的特有用法。'vicious circle' 是英语习语（我不知道它是否仅限于英语）。任何你希望不要成为循环的事件序列（无论是生活中还是编程中）都可以称为 'vicious circle'。 - Daniel Pratt

好的，我没有注意到引用文本也使用了这个术语。我以为这可能是OP想出来描述情况的东西。无论如何，我认为这不是一个非常有用的术语。 "非终止"、"发散"或"无限循环"都是我会很容易地与这个概念联系起来的术语 :) - Gian

Answer 3

Haskell的一个显著特点是它的惰性。列表仅是其中一部分。基本上，Haskell在以下情况下才执行任何计算:

1. 需要计算值来计算其他必需的值...
2. 您要求Haskell比它本来可能做的更早地进行某些计算。

因此，primes1函数生成一个Integer值列表，但仅生成必要的值以满足整个计算。即使如此，如果您按以下方式定义它：

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

您会遇到一个问题。 primes1 将尝试通过（间接）评估prime 2来生成其序列中的第一个值，这将评估ldp 2，它将要求由primes1产生的第一个值...无限循环！通过直接返回2作为primes1生成的序列的第一个值，您可以避免无限循环。对于序列中生成的每个后续值，primes1已经生成了一个先前的值，该值将由ldp在计算后续值时进行评估。

- Daniel Pratt