我试图理解这里列举的素数算法之一:https://wiki.haskell.org/index.php?title=Prime_numbers&oldid=36858#Postponed_Filters_Sieve,具体来说:
primes :: [Integer]
primes = 2: 3: sieve (tail primes) [5,7..]
where
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, x `rem` p /= 0]
-- or: filter ((/=0).(`rem`p)) t
where (h,~(_:t)) = span (< p*p) xs
所以在概念上,我理解这个算法是如何工作的(筛除的擦除),从2,3和一个数字列表开始,然后消除任何大于上一个平方的,可以被下一个平方整除的。
但是我很难遵循嵌套递归步骤(prime calles sieven on primes,which calls sieven on primes which…)
我知道,这是由于懒惰的评估,它显然产生了正确的结果,但我无法遵循它。
例如,如果我运行
take 5 primes
实际会发生什么:例如(为了便于阅读/推理,我将take操作的结果称为t):
步骤1)
primes返回一个列表
[2,3, xs]
所以
t
就是[2,3, take 3 xs]
其中
xs
是sieve (tail primes) [5,7..]
步骤2)
tail primes
是3:xs
其中
xs
是sieve (tail primes) [5,7..]
等
所以t现在应该是[2,3,3,3,3,3…]
我很难跟踪筛子本身…
所以我想我有两个问题。
1)这个算法到底是如何工作的,我的跟踪哪里/为什么错了
2)在Haskell中,有没有一种方法可以确定事物运行的顺序?也许打印一个递归树?或者至少让调试器停止?
最佳答案
我冒昧地对算法进行了一些去优化和澄清:
primes :: [Integer]
primes = 2 : sieve primes [3 ..]
sieve :: [Integer] -> [Integer] -> [Integer]
sieve [] xs = xs -- degenerate case for testing
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, x `rem` p /= 0]
where (h, t) = span (< p*p) xs
这是相同的基本逻辑,但它比您提供的版本做了更多的冗余工作(尽管是每个输出值的常数)。我认为这是一个简单的起点,一旦你了解了这个版本的工作原理,就很容易看出优化的作用。我还将
sieve
引入了它自己的定义。它没有使用封闭范围中的任何东西,独立测试它的能力可能有助于理解发生了什么。如果您想了解评估是如何进行的,可以使用
Debug.Trace
模块。我最常用的两个函数是trace
和traceShow
,这取决于我想看到的值。所以,让我们从
sieve
中获取一些跟踪信息:import Debug.Trace
primes :: [Integer]
primes = 2 : sieve primes [3 ..]
sieve :: [Integer] -> [Integer] -> [Integer]
sieve [] xs = trace "degenerate case for testing" xs
sieve (p:ps) xs = traceShow (p, h) $ h ++ sieve ps [x | x <- t, x `rem` p /= 0]
where (h, t) = span (< p*p) xs
为了测试它:
ghci> take 10 primes
[2(2,[3])
,3(3,[5,7])
,5,7(5,[11,13,17,19,23])
,11,13,17,19,23(7,[29,31,37,41,43,47])
,29]
好吧,这远没有想象中那么清楚。当ghci输出结果时,它使用
Show
实例作为结果的类型。而Show
的[Integer]
实例本身是惰性的,因此列表的打印与跟踪是交错的为了做得更好,让ghci生成一个值,直到跟踪完成之后才会输出。sum
应该:ghci> sum $ take 10 primes
129
那是不太有用追踪到哪里去了?好吧,记住跟踪函数是非常不纯洁的。他们明确的目标是产生副作用但ghc不尊重副作用。它假设所有函数都是纯函数。这种假设的一个结果是,它可以存储计算表达式的结果。(是否这样做取决于是否有共享引用或CSE优化启动。在这种情况下,
primes
本身就是一个共享引用。)如果我们要求它比目前更进一步的评估呢?
ghci> sum $ take 20 primes
(11,[53,59,61,67,71,73,79,83,89,97,101,103,107,109,113])
639
好的,跟踪是根据需要从ghci的输出中分离出来的但在这一点上,它的信息量并不大。为了得到更好的图片,它需要从头开始。为此,我们需要让ghci卸载素数的定义,以便它从头开始重新评估它。有很多方法可以做到这一点,但我将演示一种方法,它有一些其他有用的方法。
ghci> :load *sieve.hs
[1 of 1] Compiling Main ( sieve.hs, interpreted )
Ok, modules loaded: Main.
通过在
*
命令中将:load
放在文件名前面,我指示ghci从头开始解释源代码,而不管其当前状态如何。这在本例中有效,因为它强制重新解释,即使源代码没有更改。当您希望在当前目录中已编译输出的源上使用:load
并让它解释整个模块(而不仅仅是加载编译的代码)时,它也很有用。ghci> sum $ take 10 primes
(2,[3])
(3,[5,7])
(5,[11,13,17,19,23])
(7,[29,31,37,41,43,47])
129
现在,让我们来了解一下算法的实际工作原理。首先要了解跟踪输出的组件是什么。第一个元素是素数,其倍数被筛选出潜在的输出。第二个元素是被接受为素数的值的列表,因为它们小于
p*p
,并且所有小于该值的非素数都已从候选列表中删除。对埃拉托舍内斯筛子的任何研究都应该熟悉其机理。对
sieve
的调用从sieve primes [3..]
开始。懒惰首先起关键作用的是第一个论点上的模式匹配(:)
构造函数是已知的,因此模式将p
与文本2
匹配,并将ps
与未计算的表达式匹配它的未评估非常重要,因为对sieve
的调用是计算值的方法如果强制对其进行求值,则会引入循环数据依赖关系,从而导致无限循环。如跟踪所示,用于从候选元素中移除元素的素数是2。调用
span
将输入[3..]
拆分为([3], [4..])
。h
是[3]
,如跟踪输出所示。所以调用sieve
的结果是[3] ++ <recursive call to sieve>
。这是懒惰在算法中起关键作用的第二位。(++)
的实现在生成列表的前缀之前,不会对其第二个参数执行任何操作。这意味着在对sieve
的递归调用求值之前,已知ps
指的是求值为[3] ++ <recursive call>
的thunk。这些信息足以处理对
sieve
的递归调用。现在,p
与3
匹配,ps
与thunk匹配,逻辑继续。追踪应该能说明这一点上发生了什么。现在,您开始使用的版本做了一些优化工作首先,它观察到
t
的第一个元素总是等于p*p
,它使用模式匹配来消除该元素,而无需对其进行任何余数计算这是一个小储蓄每次质素检查,但这是一个明确的储蓄。其次,它跳过了过滤掉2的倍数,只是一开始没有生成它们。这样可以将生成的要在以后进行过滤的元素数量减少两倍,并且可以将应用于每个奇数元素的过滤器数量减少一倍。
另外,请注意,叠加滤波器的行为实际上在算法上是重要的,并且不符合文献中所述的埃拉托舍内斯筛关于这方面的进一步讨论,见梅丽莎·奥尼尔的《aa》。