On Sun, Dec 6, 2015 at 10:24 AM, Daniel Bergey <bergey@alum.mit.edu> wrote:

> data Li a = Nil | Cons a (Li a)
> deriving (Show)
>
> instance Foldable Li where
> foldr f b Nil = b
> foldr f b (Cons a y) = foldr f (f a b) y
>
> So I'm trying out foldr for my type:
>> foldr Cons Nil (Cons 1 (Cons 2 Nil))
> Cons 2 (Cons 1 Nil)
>
> This shows my foldr implementation i'm not folding from right side,
> but how can I possibly do that - the data could have been an infinite
> stream.

A right fold on an infinite stream can terminate if the function f
sometimes discards it's second argument. For example, takeWhile can be
implemented this way.

You are right that `foldr Cons Nil` or `foldr (:) []` will not terminate
on an infinite list.

It's slightly misleading to say: `foldr (:) []` -- call it the foo fold -- will not terminate on an infinite list.

It suggests that folds normally terminate on an infinite list whereas this one doesn't, with the implied meaning that the foo fold is "defective" in some sense.

Fact is, the foo fold is perfectly cromulent. It's equivalent to the identity function on both finite and infinite lists. So the foo fold doesn't terminate on an infinite list because -- well, duh -- the infinite list doesn't terminate.

Also not all folds are designed to terminate. E.g. a list map makes sense even for infinite lists. A list map can be written as a fold. Such a fold wouldn't terminate either.

-- Kim-Ee