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

[Daniel Bergey]

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.

bergey