Why wouldn't my sieve terminate when I rewrote it as a foldl?

Question

What's the specific problem with my foldl that prevents it from terminating or producing output?

First I achieved a sieve for primes. It's not the best, but it works just fine as (for example) 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

Then I thought it would be more Haskell-y to eliminate the counter i using foldl as follows. But this is not effective.

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

It neither terminates nor produces any output when I run (for example) head primesB.

Presumably ghci is looking at the infinitely many lists of multiples of primes in its vain attempt to attain the value of the head of the list.

But why specifically does it do that?

Answer 1

foldl can't ever terminate on an infinite list. This is the definition of the function:

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

Notice that in Haskell, when you force a thunk, evaluation only stops when we reach a step where the outermost operation is a data constructor (well, unless you use explicit forcing or lazy pattern matching). In the case of foldl, that can only be when it hits []. Let's look at this example, reversing an infinite list (which should give it away already):

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

Since foldl will always be the outermost operator, and foldl is not a constructor, it will never terminate. With some reflection you can see that no left fold of an infinite list can ever terminate.

foldr doesn't have that problem because its second equation has f at the top:

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

Example:

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

Now (:) is the outermost operator, so evaluation stops here; something has to force the constructor's arguments for evaluation to continue.