haskell - 解释这段输出素数流的haskell代码

Question

我很难理解这段代码:

let
  sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]

有人可以为我分解吗？我知道其中存在递归，但这就是我无法理解此示例中的递归如何工作的问题。

Answer 1

与其他人在这里所说的相反，这个函数 does not 实现真正的sieve of Eratosthenes .它确实返回了一个初始的素数序列，并且以类似的方式，因此可以将其视为 Eratosthenes 的筛子。

当 mipadi posted 时，我即将完成对代码的解释。他的回答；我可以删除它，但由于我花了一些时间，而且因为我们的答案并不完全相同，所以我将它留在这里。

首先，请注意您发布的代码中存在一些语法错误。正确的代码是，

let sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) in sieve [2..]

let x in y定义 x并允许在 y 中使用其定义.此表达式的结果是 y 的结果.所以在这种情况下，我们定义了一个函数 sieve并返回应用 [2..] 的结果至sieve .

现在让我们仔细看看let这个表达式的一部分:

sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)

这定义了一个函数 sieve它将一个列表作为它的第一个参数。

(p:xs)是匹配 p 的模式与上述名单的负责人和xs有尾部(除了头以外的一切)。

一般情况下，p : xs是一个列表，其第一个元素是 p . xs是一个包含剩余元素的列表。因此，sieve返回它接收到的列表的第一个元素。

不看列表的其余部分:

sieve (filter (\x -> x `mod` p /= 0) xs)

我们可以看到 sieve被递归调用。因此，filter表达式将返回一个列表。

filter 接受一个过滤器函数和一个列表。它仅返回列表中过滤器函数为其返回 true 的那些元素。

在这种情况下 xs是被过滤的列表并且

(\x -> x `mod` p /= 0)

是过滤功能。

过滤器函数采用单个参数 x如果它不是 p 的倍数，则返回 true .

现在 sieve已定义，我们通过 [2 .. ] ，从 2 开始的所有自然数的列表。因此，

将返回数字 2。所有其他为 2 的倍数的自然数将被丢弃。

因此，第二个数字是 3。它将被返回。所有其他 3 的倍数将被丢弃。

因此下一个数字将是 5。等等。