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? Even the function passed to foldl has 3 parameters when a function of 2 is needed. What is the precedence and associativity involved here that makes foldr' a valid expression? Thanks! -- 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.
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!
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
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
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.
Daniel Fischer wrote:
id id id id id ... id x
Federico Mastellone wrote:
This is one crazy little example
Here's an even crazier one: Use :t in ghci to look at the types of these: (.) (.)(.) (.)(.)(.) etc. Hint: after a while, it starts repeating. Regards, Yitz
participants (3)
-
Daniel Fischer -
Federico Mastellone -
Yitzchak Gale