<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Dec 6, 2015 at 10:24 AM, Daniel Bergey <span dir="ltr"><<a href="mailto:bergey@alum.mit.edu" target="_blank">bergey@alum.mit.edu</a>></span> wrote:<br><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
> data Li a = Nil | Cons a (Li a)<br>
>     deriving (Show)<br>
><br>
> instance Foldable Li where<br>
>     foldr f b Nil = b<br>
>     foldr f b (Cons a y) = foldr f (f a b) y<br>
><br>
> So I'm trying out foldr for my type:<br>
>> foldr Cons Nil (Cons 1 (Cons 2 Nil))<br>
> Cons 2 (Cons 1 Nil)<br>
><br>
> This shows my foldr implementation i'm not folding from right side,<br>
> but how can I possibly do that - the data could have been an infinite<br>
> stream.<br>
<br>
</span>A right fold on an infinite stream can terminate if the function f<br>
sometimes discards it's second argument.  For example, takeWhile can be<br>
implemented this way.<br>
<br>
You are right that `foldr Cons Nil` or `foldr (:) []` will not terminate<br>
on an infinite list.</blockquote></div><br></div><div class="gmail_extra">It's slightly misleading to say: `foldr (:) []` -- call it the foo fold -- will not terminate on an infinite list.<br><br></div><div class="gmail_extra">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.<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">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.<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">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.<br></div><div class="gmail_extra"><br></div><div class="gmail_extra"><div><div class="gmail_signature">-- Kim-Ee</div></div>
</div></div>