我无法理解这段代码:
let sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs) in sieve [2 .. ]
有人可以为我分手吗？我知道它有递归,但这就是问题我无法理解这个例子中的递归是如何工作的.
与其他人在此处所述相反,此功能并未实现Eratosthenes的真正筛选.它确实返回了素数的初始序列,并且以类似的方式,因此可以将其视为Eratosthenes的筛子.
当mipadi 发布他的回答时,我就完成了对代码的解释; 我可以删除它,但是因为我花了一些时间在它上面,而且因为我们的答案不完全相同,所以我会把它留在这里.
首先,请注意您发布的代码中存在一些语法错误.正确的代码是,
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)是一种与所述列表的头部和尾部(除头部之外的所有部分)匹配的模式.pxs
通常,p : xs是第一个元素是的列表p.xs是包含其余元素的列表.因此,sieve返回它接收的列表的第一个元素.
不看列表的其余部分:
sieve (filter (\x -> x `mod` p /= 0) xs)
我们可以看到这sieve是递归调用的.因此,filter表达式将返回一个列表.
filter采用过滤功能和列表.它仅返回列表中过滤器函数返回true的那些元素.
在这种情况下xs,列表被过滤和
(\x -> x `mod` p /= 0)
是过滤功能.
filter函数只接受一个参数,x如果它不是倍数,则返回true p.
现在sieve已定义,我们传递它[2 .. ],从2开始的所有自然数列表.因此,
将返回2号.所有其他自然数是2的倍数将被丢弃.
因此第二个数字是3.它将被退回.所有其他3的倍数将被丢弃.
因此,下一个数字将是5.等.
它实际上非常优雅.
首先,我们定义一个sieve带有元素列表的函数:
sieve (p:xs) =
在sieve我们的主体中,我们采用列表的头部(因为我们传递了无限列表[2..],并且2被定义为素数)并将其(懒惰!)附加到应用于sieve列表其余部分的结果中:
p : sieve (filter (\ x -> x 'mod' p /= 0) xs)
那么让我们看看在列表的其余部分进行工作的代码:
sieve (filter (\ x -> x 'mod' p /= 0) xs)
我们正在申请sieve过滤列表.让我们分解过滤器部分的作用:
filter (\ x -> x 'mod' p /= 0) xs
filter获取一个函数和一个列表,我们应用该函数,并保留符合函数给出的条件的元素.在这种情况下,filter采取匿名函数:
\ x -> x 'mod' p /= 0
这个匿名函数接受一个参数,x.它检查模量的x反对p(名单的头,每次sieve叫):
x 'mod' p
如果模数不等于0:
x 'mod' p /= 0
然后元素x保留在列表中.如果它等于0,则将其过滤掉.这是有道理的:如果可以x被整除p,那么可以被x1除以及它自身整除,因此它不是素数.
它定义了一个生成器 - 一个名为"筛子"的流变换器,
Sieve s =
while( True ):
p := s.head
s := s.tail
yield p -- produce this
s := Filter (nomultsof p) s -- go next
primes := Sieve (Nums 2)
它使用相当于的匿名函数的curried形式
nomultsof p x = (mod x p) /= 0
两个Sieve和Filter是数据构造与操作的内部状态和通过值参数传递语义.
在这里我们可以看到这个代码最明显的问题不是,重复不是它使用试验除法来从工作序列中滤除多个,而它可以直接找到它们,通过以增量递增计数p.如果我们用后者替换前者,那么生成的代码仍然会有非常糟糕的运行时复杂性.
不,它最明显的问题是它过早地处Filter于其工作序列的顶部,当它应该在输入中看到素数的正方形之后才真正做到这一点.因此,与真正需要的相比,它创建了二次数s.它创造的链条太长了,根本不需要它们中的大多数.FilterFilter
修正后的版本,过滤器创建推迟到适当的时刻,是
Sieve ps s =
while( True ):
x := s.head
s := s.tail
yield x -- produce this
p := ps.head
q := p*p
while( (s.head) < q ):
yield (s.head) -- and these
s := s.tail
ps := ps.tail -- go next
s := Filter (nomultsof p) s
primes := Sieve primes (Nums 2)
或者在Haskell,
primes = sieve primes [2..]
sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem x p /= 0]
where (p:pt) = ps
(h,t) = span (< p*p) xs
rem在这里使用而不是mod因为它在一些解释器中可以更快,并且无论如何数字都是正数.
通过在问题大小的点上运行其运行时间来测量算法的局部增长顺序,因为我们获得第一个,并且恰好在第二个上方(在产生的素数中).t1,t2n1,n2logBase (n2/n1) (t2/t1)O(n^2)O(n^1.4)n
只是为了澄清它,缺少的部分可以用这个(想象的)语言来定义
Nums x = -- numbers from x
while( True ):
yield x
x := x+1
Filter pred s = -- filter a stream by a predicate
while( True ):
if pred (s.head) then yield (s.head)
s := s.tail
另见.
更新:奇怪的是,根据AJT Davie 1992年的Haskell书,David Turner 1976年SASL手册中的第一个代码实例,
primes = sieve [2..]
sieve (p:nos) = p : sieve (remove (multsof p) nos)
实际上承认了两 对实现remove并且multsof一起进行 - 一对用于试验分区筛,如同在这个问题中,另一对用于有序去除每个素数的直接由计数产生的倍数,也就是真正的Eratosthenes筛(两者都是当然没有延期).在哈斯克尔,
multsof p n = rem n p==0 remove m xs = filter (not . m) xs
multsof p = [p*p, p*p+p..] remove m xs = diff xs m
(如果只是他推迟了选择实际的实施......)
至于推迟的代码,在具有"列表模式" 的伪代码中,它可能已经存在
primes = [2, ...sieve primes [3..]]
sieve [p, ...ps] [...h, p*p, ...nos] =
[...h, ...sieve ps (remove (multsof p) nos)]
京公网安备 11010802040832号 | 京ICP备19059560号-6 