[Haskell-beginners] Data.Foldable's foldr'

[Federico Mastellone]

Thanks Yitzchak and Daniel (again)

I think I looked at this code in a non-functional way! I was expecting, no
matter what, the fold to return a value and not a function, so my head, or
HHC (Head Haskell Compiler), was throwing a syntax error!

This is one crazy little example
id id id id id ... id x

Regards!

On Wed, Jun 15, 2011 at 12:38 PM, Yitzchak Gale <gale at sefer.org> wrote:

> Federico Mastellone wrote:
> > foldl :: (a -> b -> a) -> a -> t b -> a
> >
> > Them, outside of the class, foldr' is defined like this:
> >
> > -- | Fold over the elements of a structure,
> > -- associating to the right, but strictly.
> > foldr' :: Foldable t => (a -> b -> b) -> b -> t a -> b
> > foldr' f z0 xs = foldl f' id xs z0
> >   where f' k x z = k $! f x z
> >
> > I don't understand this definition, foldl receives 3 parameters and here
> it
> > is used with 4, how is it possible?
> > Even the function passed to foldl has 3 parameters when a function of 2
> is
> > needed.
>
> In the type of foldl, the parameter 'a' can be any type - even
> a function.
>
> So let's see what we get when we substitute 'c -> d' for 'a'
> in the type of foldl:
>
> ((c -> d) -> b -> (c -> d)) -> (c -> d) -> t b -> (c -> d)
>
> Now, remembering that -> is right-associative
> in type expressions, we can remove some parentheses:
>
> ((c -> d) -> b -> c -> d) -> (c -> d) -> t b -> c -> d
>
> So when 'a' is a function, we see that foldl indeed takes
> 4 parameters, and its first parameter is a function that
> takes 3 parameters.
>
> Regards,
> Yitz
>



-- 
Federico Mastellone
Computer Science Engineer - ITBA

".. there are two ways of constructing a software design: One way is to make
it so simple that there are obviously no deficiencies, and the other way is
to make it so complicated that there are no obvious deficiencies. The first
method is far more difficult."

Tony Hoare, 1980 ACM Turing Award Lecture.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20110616/e0593d9e/attachment.htm>