当我把它重写成折叠时,为什么我的筛子不会终止？

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

然后我认为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正在寻找无数多个素数列表,这是徒劳地试图获得列表头部的价值.

但为什么要这样做呢？

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

现在(:)是最外面的运营商,所以评估在这里停止; 某些东西必须强制构造函数的参数继续进行评估.