5

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

i然后我认为使用foldl如下方式消除计数器会更Haskell-y 。但这并不有效。

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 正在查看无限多的素数倍数列表，试图获得列表头部的值是徒劳的。

但它为什么专门这样做呢？

4

3 回答 3

11

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..]

Now(:)是最外层的操作符，所以评估在这里停止；有些东西必须强制构造函数的参数继续进行评估。

于 2013-04-29T05:28:33.370 回答
2

（澄清：这或多或少地重复了我在 https://cstheory.stackexchange.com/ 上对您的问题的回答的最后一部分，并对其进行了详细说明；我不确定它是否适合那里。 )

您的第一个版本实际上非常接近 Richard Bird 的解决方案（来自 M. O'Neill 论文的第 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

这段代码有两个问题。有一种(...(((a+b)+c)+d)+...)计算结构，它使产生频率较高的流在结构中的位置低于产生频率较低的流。

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

我们可以在素数的平方上显式同步，取自素数序列本身，因为它正在生成（这只是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 ..])

现在距离 Richard Bird 的解决方案仅半步之遥，该解决方案巧妙地解决了这两个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，所以什么都不加。

于 2013-05-29T18:23:30.780 回答
0

对于任何可能想知道如何更正我的代码primesB的人，以下修订版将起作用。正如 Klaus Draeger在 cstheory.se 中所写的那样，它将“正确地交错各个头部” 。它相当于，虽然可能不如理查德伯德在我奥尼尔埃拉托色尼的真正筛子第 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`.

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

于 2013-05-05T02:46:29.960 回答