haskell - 为什么 Eratosthenes 的筛选需要额外的辅助函数来合并无限列表？

Question

我正在使用来自 Literate Programming ( http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29 ) 的 Eratosthenes 代码筛选器，稍作修改以包括合并和差异的边缘情况:

primesInit = [2,3,5,7,11,13]
primes = primesInit ++ [i | i <- diff [15,17..] nonprimes]

nonprimes = foldr1 f . map g $ tail primes
        where g p = [n * p | n <- [p,p+2..]]
              f (x:xt) ys = x : (merge xt ys)

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xs@(x:xt) ys@(y:yt)
    | x < y  = x : merge xt ys
    | x == y = x : merge xt yt
    | x > y  = y : merge xs yt

diff :: (Ord a) => [a] -> [a] -> [a]
diff [] ys = []
diff xs [] = xs
diff xs@(x:xt) ys@(y:yt)
    | x < y  = x : diff xt ys
    | x == y = diff xt yt
    | x > y  = diff xs yt

merge 和 diff 本身都是懒惰的。非素数和素数也是如此。但是如果我们改变素数的定义以移除 f，如下所示:

nonprimes = foldr1 merge . map g $ tail primes
        where g p = [n * p | n <- [p,p+2..]]

现在非素数并不懒惰。我也用 take 20 $ foldr1 merge [[i*n | n <- [3,7..]] | i <- [5,9..]] 重新创建了这个(GHCI 内存不足并退出)。

基于 http://www.haskell.org/haskellwiki/Performance/Laziness ，非懒惰的一个简单来源是在返回数据构造函数之前递归。但是merge没有这个问题；它返回一个包含递归调用的 cons-cell 作为第二项。 foldr 的使用本身也不应该是这里的罪魁祸首(它是 foldl 不能做无限列表)。

那么，为什么merge 需要通过f 与foldr1 分开，这本质上是手动进行第一次调用merge？ f 所做的只是返回一个 cons 单元格，其中包含对合并的调用作为第二项，对吗？

注意:Stack Overflow 上的其他人正在使用类似的代码并遇到了与我相同的问题，但他们接受了一个在我看来基本上是不同代码的答案。我问的是为什么，而不是如何，因为在 Haskell 中懒惰似乎有些重要。

Answer 1

让我们再次比较这两个函数:

merge [] ys = ys
merge xs [] = xs
merge xs@(x:xt) ys@(y:yt)
    | x < y  = x : merge xt ys
    | x == y = x : merge xt yt
    | x > y  = y : merge xs yt

和

f (x:xt) ys = x : (merge xt ys)

让我们忽略两者之间的语义差异，尽管它们很重要 - f就何时有效调用而言受到更多限制。相反，让我们只看严格性属性。

自上而下检查多个方程中的模式匹配。从左到右检查单个方程中的多个模式匹配。所以第一件事 merge do 是强制其第一个参数的构造函数，以确定第一个方程是否匹配。如果第一个方程不匹配，它会强制第二个参数的构造函数，以确定第二个方程是否匹配。只有当两个方程都不匹配时，它才会移动到第三种情况。编译器足够聪明，知道此时它已经强制使用了两个参数，因此它不会再次执行此操作——但是如果这些模式匹配还没有强制使用参数，则这些模式匹配将需要强制使用参数。

但这里重要的是，找出哪个方程匹配的过程会导致在生成任何构造函数之前强制执行这两个参数。

现在，对比一下 f .在 f的定义中，唯一的模式匹配是在第一个参数上。因此， f比 merge 严格一些.它在检查第二个参数之前生成一个构造函数。

事实证明，如果您仔细检查 foldr 的行为，当传递给它的函数在生成构造函数之前没有(总是)检查它的第二个参数时，它恰好适用于无限列表。

括号里的“总是”很有趣。我最喜欢的使用示例之一 foldr和懒惰在一起是:

dropRWhile :: (a -> Bool) -> [a] -> [a]
dropRWhile p = foldr (\x xs -> if p x && null xs then [] else x:xs) []

这是一个最大延迟函数，其工作方式类似于 dropWhile ，除了列表的后面(右侧)。如果当前元素与谓词不匹配，则立即返回。如果它确实匹配谓词，它会向前看，直到找到不匹配或列表末尾的内容。只要最终找到与谓词不匹配的元素，这将在无限列表上产生效果。这就是上面“总是”括号的来源 - 通常在生成构造函数之前不检查其第二个参数的函数仍然允许 foldr 通常在无限列表上工作。