[Haskell-beginners] foldr, Foldable and right-side folding

[Kim-Ee Yeoh]

On Sun, Dec 6, 2015 at 10:24 AM, Daniel Bergey <bergey at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20151212/fb78e49f/attachment.html>