[Haskell-beginners] Data.Foldable's foldr'
Daniel Fischer
daniel.is.fischer at googlemail.com
Wed Jun 15 17:36:01 CEST 2011
On Wednesday 15 June 2011, 17:17:46, Federico Mastellone wrote:
> Hi,
>
> Looking at the source of Data.Foldable I found something I don't
> understand
>
> The Foldable class declares foldl like this:
>
> 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
> -> bfoldr' 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?
The result is a function, which is then applied to the value z0
foldr' f z0 xs =
let res :: b -> b
res = foldl f' id xs
f' :: (b -> b) -> a -> b -> b
f' k x z = k $! f x z
in res z0
Since the function arrow (->) associates to the right, the type of f' can
also be written
f' :: (b -> b) -> a -> (b -> b)
This is an example illustrating that the concept of arity isn't easy in
Haskell (unless you resolve to "every function has arity 1").
Also
id id id id id ... id x
>
> Even the function passed to foldl has 3 parameters when a function of
> 2 is needed.
The third argument is the argument of the resulting function.
>
> What is the precedence and associativity involved here that makes
> foldr' a valid expression?
Function application has the highest precedence and associates to the left
foldl f' id xs z0
= (foldl f' id xs) z0
= ((foldl f' id) xs) z0
= (((foldl f') id) xs) z0
>
> Thanks!
More information about the Beginners
mailing list