[Haskell-beginners] Data.Foldable's foldr'
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:
> Looking at the source of Data.Foldable I found something I don't
> 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").
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
More information about the Beginners