我试图理解这里列举的素数算法之一: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]
其中xssieve (tail primes) [5,7..]
步骤2)
tail primes3:xs
其中xssieve (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模块。我最常用的两个函数是tracetraceShow,这取决于我想看到的值。
所以,让我们从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的递归调用。现在,p3匹配,ps与thunk匹配,逻辑继续。追踪应该能说明这一点上发生了什么。
现在,您开始使用的版本做了一些优化工作首先,它观察到t的第一个元素总是等于p*p,它使用模式匹配来消除该元素,而无需对其进行任何余数计算这是一个小储蓄每次质素检查,但这是一个明确的储蓄。
其次,它跳过了过滤掉2的倍数,只是一开始没有生成它们。这样可以将生成的要在以后进行过滤的元素数量减少两倍,并且可以将应用于每个奇数元素的过滤器数量减少一倍。
另外,请注意,叠加滤波器的行为实际上在算法上是重要的,并且不符合文献中所述的埃拉托舍内斯筛关于这方面的进一步讨论,见梅丽莎·奥尼尔的《aa》。

10-06 10:31