解释这段输出素数流的haskell代码 [英] Explain this chunk of haskell code that outputs a stream of primes

问题描述

我无法理解这段代码:

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

谁能帮我分解一下?我知道其中存在递归，但这就是我无法理解此示例中的递归如何工作的问题.

Can someone break it down for me? I understand there is recursion in it, but thats the problem I can't understand how the recursion in this example works.

推荐答案

其实很优雅.

首先，我们定义一个函数sieve，它接受一个元素列表:

First, we define a function sieve that takes a list of elements:

sieve (p:xs) =

在sieve的主体中，我们取了列表的头部(因为我们传递的是无限列表[2..]，并且2被定义为成为质数)并将其(懒惰地！)附加到将 sieve 应用于列表的其余部分的结果:

In the body of sieve, we take the head of the list (because we're passing the infinite list [2..], and 2 is defined to be prime) and append it (lazily!) to the result of applying sieve to the rest of the list:

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

那么让我们看看对列表的其余部分进行工作的代码:

So let's look at the code that does the work on the rest of the list:

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

我们正在将 sieve 应用于过滤列表.让我们分解过滤器部分的作用:

We're applying sieve to the filtered list. Let's break down what the filter part does:

filter ( x -> x 'mod' p /= 0) xs

filter 接受一个函数和一个我们应用该函数的列表，并保留满足函数给定条件的元素.在这种情况下，filter 采用匿名函数:

filter takes a function and a list on which we apply that function, and retains elements that meet the criteria given by the function. In this case, filter takes an anonymous function:

 x -> x 'mod' p /= 0

这个匿名函数接受一个参数，x.它根据 p(列表的头部，每次调用 sieve 时)检查 x 的模:

This anonymous function takes one argument, x. It checks the modulus of x against p (the head of the list, every time sieve is called):

 x 'mod' p

如果模数不等于0:

 x 'mod' p /= 0

然后元素 x 被保留在列表中.如果它等于 0，则将其过滤掉.这是有道理的:如果 x 可以被 p 整除，那么 x 可以被 1 和它本身整除，因此它不是质数.

Then the element x is kept in the list. If it is equal to 0, it's filtered out. This makes sense: if x is divisible by p, than x is divisible by more than just 1 and itself, and thus it is not prime.

这篇关于解释这段输出素数流的haskell代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！