algorithm - 有没有一种方法可以接收有关执行顺序的信息(特别是用于eratosthenes筛子)？

Question

我试图理解这里列举的素数算法之一：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中，有没有一种方法可以确定事物运行的顺序？也许打印一个递归树？或者至少让调试器停止？

Answer 1

我冒昧地对算法进行了一些去优化和澄清：

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》。