为什么当我将它重写为foldl时，我的筛没有终止？

Question

我的foldl的具体问题是什么，导致它无法终止或生成输出？

首先我实现了素数筛。这不是最好的，但它工作得很好（例如）take 20 primesA。

primesA :: [Integer] 
primesA = sieve 2 [] 

sieve :: Integral a => a -> [a] -> [a] 
sieve i [] = (i:) $ sieve (i + 1) $ map (*i) [i ..] 
sieve i composites@(h : t) 
    | i == h =  sieve (i + 1) t 
    | otherwise = (i:) $ sieve (i + 1) $ unionIncreasing composites $ map (*i) [i ..] 

unionIncreasing :: Ord a => [a] -> [a] -> [a] 
unionIncreasing [] b = b 
unionIncreasing a [] = a 
unionIncreasing a@(ah:at) b@(bh:bt) | ah < bh = ah : at `unionIncreasing` b 
            | ah == bh = ah : at `unionIncreasing` bt 
            | otherwise = bh : a `unionIncreasing` bt 

然后，我认为这将是更哈斯克尔-Y消除使用foldl如下柜台i。但这不是有效的。

primesB :: [Integer] 
primesB = [2..] `differenceIncreasing` composites 

composites :: [Integer] 
composites = foldl f [] [2..] 
    where f [] i = map (*i) [i ..] 
     f knownComposites@(h:t) i | i == h = knownComposites 
            | otherwise = (h:) $ unionIncreasing t $ map (*i) [i ..] 

differenceIncreasing :: Ord a => [a] -> [a] -> [a] 
differenceIncreasing [] b = [] 
differenceIncreasing a [] = a 
differenceIncreasing (x:xs) (y:ys) | x < y = x : xs `differenceIncreasing` (y:ys) 
            | x == y = xs `differenceIncreasing` ys 
            | otherwise = (x:xs) `differenceIncreasing` ys 

它既不终止也不产生当我运行（例如）head primesB任何输出。

据推测，ghci正在寻找无数次的素数倍数列表，以妄图获得列表头的价值。

但是，为什么它具体做到这一点？

Answer 1

foldl永远无法在无限列表上终止。这是函数的定义：

foldl :: (b -> a -> b) -> b -> [a] -> b 
foldl f z [] = z 
foldl f z (x:xs) = foldl f (f z x) xs 

注意，在Haskell，当你强迫一个thunk，评价只有当我们到达一个步骤，其中最外面的操作是数据的构造函数（当然，除非你使用显式强制停止或懒惰模式匹配）。在foldl的情况下，只有当它遇到[]时才可以。让我们来看看下面这个例子，扭转了无限列表（这应该送人的话）：

foldl (flip (:)) [] [1..] 
    = foldl (flip (:)) [1] [2..] 
    = foldl (flip (:)) [2, 1] [3..] 
    = foldl (flip (:)) [3, 2, 1] [4..] 
    = foldl (flip (:)) [4, 3, 2, 1] [5..] 
    . 
    . 
    . 

由于foldl永远是最外面的运营商，而foldl不是构造函数，它永远不会终止。通过一些反思，你可以看到无限列表的左边折不能终止。

foldr不存在这样的问题，因为它的第二个方程f顶部：

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z [] = z 
foldr f z (x:xs) = f x (foldr f z xs) 

例子：

foldr (:) [] [1..] 
    = 1 : foldr (:) [] [2..] 

现在(:)是最外面的运营商，所以评价止于此;有些东西不得不迫使构造者的评论继续下去。

Answer 2

对于任何人可能想知道如何更正我的代码primesB，以下修订将工作。它将“正确地交错各个头”，正如Klaus Draeger在cstheory.se中写下here。这相当于，虽然比也许更少赏心悦目，埃拉托色尼的真正筛归因于理查德·伯德ME第11页奥尼尔的代码：http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf（感谢@Wes）打印为：http://dx.doi.org/10.1017/S0956796808007004

primesB :: [Integer] 
-- #1 necessary change 
-- primesB = [2..] `differenceIncreasing` composites 
primesB = 2 : [3..] `differenceIncreasing` composites 

-- #2 necessary change, entire function 
composites = foldr f [] primesB -- not foldl, not [2..] 
    where f :: Integer -> [Integer] -> [Integer] 
     -- no destructuring of knownComposites; 
     -- square the first list element and don't put that in unionIncreasing's second argument 
     f i knownComposites = ((i*i):) $ unionIncreasing knownComposites $ map (*i) [(i+1)..] 

-- No change needed in `unionIncreasing` and `differenceIncreasing`. 

我仍然不确定一个人是如何实现这个解决方案的，除非它只是通过试验和错误。

Answer 3

_{（说明：此重复或多或少紧密的最后一部分的my answer to your question on https://cstheory.stackexchange.com/并在其上阐述了一下，我不知道这是否是一个不错的选择存在与否）}

你第一个版本实际上，它与理查德伯德的解决方案非常接近（见M.奥尼尔论文第11页）。你可以不通过试验和错误，而是通过代码转换和逐步改进。

一些重命名后，预先计算的第一步给了我们这个很漂亮代码：

--  map (*i) [i ..] == map (*i) [i, i+1 ..] == [i*i, i*i+i ..] 
--  sieve 2 [] where sieve i [] = (i:) $ 
--    sieve (i + 1) [i*i, i*i+i ..] == 2 : sieve 3 [4, 6 ..] 

primesA :: [Integer] 
primesA = 2 : sieve 3 [4, 6 ..] 

sieve p cs@(c : t) 
    | p == c =  sieve (p + 1) t 
    | otherwise = p : sieve (p + 1) (unionI cs [p*p, p*p+p ..]) 

unionI a@(x:xs) b@(y:ys) | x < y = x : xs `unionI` b 
         | x == y = x : xs `unionI` ys 
         | otherwise = y : a `unionI` ys 

有两个问题与此代码。有计算结构，这种结构比生产率较低的结构更低的结构。

但更为直接的问题是每个素数倍数的过早处理。例如。当您达到5时，将[25, 30 ..]添加到复合材料中。但是这只能在达到25时完成。这样做会从根本上减少在每个时刻正在处理的多个数据流的总数（从Θ(n)到Θ(sqrt(n/log n))，对于n-prime）。这对效率有非常显着的影响。

我们可以明确地同步素数的平方，在素数序列本身生成的时候从素数序列本身取得（这只是将一个单独的反向指针ps保存到序列中，该序列比生产点慢得多） ：

primesAC = [2,3] ++ sieve 4 (tail primesAC) 9 [4,6..] 

sieve k ps@(p:pt) q cs@(c:ct)     -- candidate "k", prime "p" 
    | k == c =  sieve (k + 1) ps q ct  -- square "q", composite "c" 
    | k < q = k : sieve (k + 1) ps q cs 
    | otherwise = sieve k  pt (head pt^2)  -- k == q == p*p 
         (unionI cs [q, q+p ..]) 

这现在只是半步之遥，从理查德·伯德的解决方案，修复都问题一个巧妙使用foldr，建立每个新总理的倍数流从黄金的启动a+(b+(c+(...)))计算结构方反正和同步数据暗示：

primesAD = (2 :) . sieve 3 . 
      foldr (\p r-> p*p : unionI [p*p+p, p*p+2*p ..] r) [] $ primesAD 

sieve p cs@(c : t)     -- == diffI [p..] cs, if p<=c 
    | p == c =  sieve (p + 1) t 
    | otherwise = p : sieve (p + 1) cs 

每个主广场产生第一无条件，防止失控访问过早强迫数据的其他部分。

因此foldr，而不是foldl，是天生适合这个问题。

---

你第二个变化是

primesB :: [Integer] 
primesB = [2..] `diffI` composites 

composites = foldl f [4,6..] [3..] 
    where 
     f cs@(h:t) i | i == h = cs  
        | otherwise = h : unionI t [i*i, i*i+i ..] 

diffI (x:xs) (y:ys) | x < y = x : xs `diffI` (y:ys) 
        | x == y =  xs `diffI` ys 
        | otherwise = (x:xs) `diffI` ys 

这显然是打算通过类似的迭代除了每个数字的数倍到混合的计算composites;麻烦的是，foldl不让我们进入它的内部计算过程，这是从来没有完成（如其他答案已经指出）。 foldl就像那样。 :)我们可以将它变成基于生产的iterate的迭代，但过早添加和倒置结构的相同问题仍然存在。加上它现在增加的所有数字倍数不只是素数的，像以前一样：

composites = foldl f [4,6..] [3..] 
-- no part of calculation of (f [4,6..] 3) is forced here, but if it were, ... 
= foldl f (f [4,6..] 3) [4..]     
= foldl f (4:unionI [6,8..] [9,12..]) [4..]  
= foldl f (4:unionI [6,8..] [9,12..]) [5..] 
= foldl f (4:union (unionI [6,8..] [9,12..]) [25,30..]) [6..] 
= foldl f (4:union (union (unionI [6,8..] [9,12..]) [25,30..]) [36,42..]) [7..] 
= .... 

而且([2..] `diffI`)是同上sieve 2，所以是添加任何内容。