Neil Brown-7 wrote:

step is of type b -> (a -> a) -> (a -> a), which does agree with (a -> b -> b)

Not quite right.. Let's rewite the function: myFoldl f z xs = foldr (step f) id xs z step f x g = \a -> g (f a x) now (from ghci): step (+) :: (Num t1) => t1 -> (t1 -> t3) -> t1 -> t3 or even: step (flip (:)) :: t -> ([t] -> t3) -> [t] -> t3 But yes, the type from my first post was wrong -- View this message in context: http://old.nabble.com/foldl-in-terms-of-foldr-tp27322307p27325072.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

Xingzhi Pan wrote:

More over, does "foldr step f id xs z" equal to "foldr (step f) id xs z"??

No, it does not. The former passes three-argument function 'step' to foldr and the later passes two-argument function which is the result of the partial application (step f). -- View this message in context: http://old.nabble.com/foldl-in-terms-of-foldr-tp27322307p27325448.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

On Tue, Jan 26, 2010 at 11:51 PM, Neil Brown wrote:

Xingzhi Pan wrote:

...

On Tue, Jan 26, 2010 at 11:24 PM, Eduard Sergeev wrote:

...

Xingzhi Pan wrote:

...

The first argument to foldr is of type (a -> b -> a), which takes 2 arguments.  But 'step' here is defined as a function taking 3 arguments.  What am I missing here?

You can think of step as a function of two arguments which returns a function with one argument (although in reality, as any curried function, 'step' is _one_ argument function anyway): step :: b -> (a -> c) -> (b -> c)

e.g. 'step' could have been defined as such: step x g = \a -> g (f a x)

to save on lambda 'a' was moved to argument list.

Right.  But then step is of the type "b -> (a -> c) -> (b -> c)".  But as the first argument to foldr, does it agree with (a -> b -> a), which was what I saw when I type ":t foldr" in ghci?

step is of type b -> (a -> a) -> (a -> a), which does agree with (a -> b -> b), the first argument to foldr (what you posted, both times, a -> b -> a, is the type of the first argument of *foldl* not foldr).  The code is building up a function (type: a -> a) from the list items, which it then applies to the initial value given to foldl.

Thanks,

Neil.

My mistake with the foldr signature. I'm a little confused with the type of step here. Can it be considered as taking 2 or 3 arguments and then the compiler has to infer to decide? Say if I, as a code reader, meet such a function defined with three formal parameters, how can I draw the conclusion of its type (and it takes 2 arguments actually)? Thanks. -- Pan, Xingzhi http://www.panxingzhi.net

f :: a -> b -> c is a function that takes an a, a b, and returns a c.

g :: (a -> b) -> c takes one argument, which is expected to be a function from a to b. g returns a c.

That stuff I mentioned before about variable binding and function application still applies. We can show that f and g have "isomorphic" types. But they are conceptually different types.

Except that f and g are not isomorphic. In fact, there exists no defined fuction g :: (a -> b) -> c (what type would (g id) be?) Perhaps you meant g :: a -> (b -> c)? Alexander Solla wrote:

On Jan 26, 2010, at 8:11 AM, Xingzhi Pan wrote:

...

I'm a little confused with the type of step here. Can it be considered as taking 2 or 3 arguments and then the compiler has to infer to decide?

The compiler is going to build up a sequence of functions. Consider the following (mathematical) function:

f(x, y, z) = x^2 + y^2 + z^2.

This is a function in three arguments. But if you bind any of them (say, x) to a value x', you end up with a function g(y,z) = f(x',y,z). This is a function in two arguments. Bind another variable, and you get another function, with one less argument. You need to bind all the variables in order to compute f for a point.

...

Say if I, as a code reader, meet such a function defined with three formal parameters, how can I draw the conclusion of its type (and it takes 2 arguments actually)?

You can derive this from the syntactic properties of types. Count the number of arrows that are not "in parentheses". That's how many arguments the function takes.

f :: a -> b -> c is a function that takes an a, a b, and returns a c.

g :: (a -> b) -> c takes one argument, which is expected to be a function from a to b. g returns a c.

That stuff I mentioned before about variable binding and function application still applies. We can show that f and g have "isomorphic" types. But they are conceptually different types.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe