[Haskell-beginners] Data.Foldable's foldr'
Yitzchak Gale
gale at sefer.org
Wed Jun 15 17:38:37 CEST 2011
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
More information about the Beginners
mailing list