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

[Raja]

On Sat, Dec 5, 2015 at 10:24 PM, Daniel Bergey <bergey at alum.mit.edu> wrote:

> On 2015-12-05 at 19:20, Raja <rajasharan at gmail.com> wrote:
> > foldr is supposed to start folding from the right side (as the name
> > suggests).
> > and this is why it is synonymous to "list construction" as I'm told
> >
> > for e.g:
> >> foldr (:) [ ] [1,2,3,4,5]
> > [1,2,3,4,5]
> >
> > In the same spirit I'm trying to construct a Foldable instance of my own
> > type:
> >
> > 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.
>
> On the bright side, you 've written a perfectly good left fold, even
> though it doesn't have quite the signature Haskell gives foldl.


I see - I did write a foldl impl.

instance Foldable Li where
    foldr f b Nil = b
    foldr f b (Cons a y) = f a (foldr f b y)

Now the `b' is getting propagated all the way to right.
Thanks.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20151206/3a8e7478/attachment.html>