Why is it sometimes possible to fold an infinite list from the right?

Question

I have been going through the excellent CIS 194 course when I got stuck on Part 5 of Homework 6. It revolves around implementing the ruler function without any divisibility testing.

I found that it is possible to build the ruler function by continuously interspersing an accumulator with values from an infinite list.

nats = [0,1,2,3,..]
[3]
[2,3,2]
[1,2,1,3,1,2,1]
[0,1,0,2,0,1,0,3,0,1,0,2,0]

Then I tried implementing this algorithm for Stream datatype which is a list without nil

data Stream a = Cons a (Stream a)

streamToList :: Stream a -> [a]
streamToList (Cons x xs) = x : streamToList xs

instance Show a => Show (Stream a) where
  show = show . take 20 . streamToList

streamFromSeed :: (a -> a) -> a -> Stream a
streamFromSeed f x = Cons x (streamFromSeed f (f x))

nats :: Stream Integer
nats = streamFromSeed succ 0

interleave x (Cons y ys) = Cons x (Cons y (interleave x ys))
foldStream f (Cons x xs) = f x (foldStream f xs)
ruler = foldStream interleave nats

As expected, I got stackoverflow error since I was trying to fold from the right. However, I was surprised to see the same algorithm work for normal infinite lists.

import Data.List

interleave x list = [x] ++ (intersperse x list) ++ [x]
ruler = take 20 (foldr interleave [] [0..])

What am I missing? Why one implementation works while the other doesn't?

Answer 1

Your interleave is insufficiently lazy. The magic thing that right folds must do to work on infinite structures is to not inspect the result of the folded value too closely before they do the first bit of computation. So:

interleave x stream = Cons x $ case stream of
    Cons y ys -> Cons y (interleave x ys)

This produces Cons x _ before inspecting stream; in contrast, your version requires stream to be evaluated a bit before it can pass to the right hand side of the equation, which essentially forces the entire fold to happen before any constructor gets produced.

You can also see this in your list version of interleave:

interleave x list = [x] ++ intersperse x list ++ [x]

The first element of the returned list (x) is known before intersperse starts pattern matching on list.

Answer 2

We can inspect the source code of foldr [src]. A less noisy version looks like:

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

Haskell does not evaluate eagerly. This thus means that, unless you need (foldr f z xs), it will not evaluate the accumulator. This thus means that f does not need the second parameter, for example because the first item x has a certain value, it will not evaluate the accumulator.

For example if we implement takeWhileNeq:

takeWhileNeq a = foldr f []
    where f x xs -> if x == a then [] else (x:xs)

if we thus run this on a list takeWhileNeq 2 [1,4,2,5], then it will not evaluate anything. If we however want to print the result it will evaluate this as:

   f 1 (foldr f [4,2,5])

and f will inspect if 1 == 2, since that is not the case, it will return (x:xs), so:

-> 1 : foldr f [4,2,5]

so now it will evaluate 4 == 2, and because this is false, it will evaluate this to:

-> 1 : (4 : foldr f [2,5])

now we evaluate 2 == 2, and since this is True, the function returns the empty list, and ingores the accumulator, so it will never look at foldr f [5]:

-> 1 : (4 : [])

For an infinite list, it will thus also result an empty list and ignore folding the rest of the list.