Hi,
I am reading Real World Haskell and have some questions about the piece of code implementing foldl in terms of foldr: -- file: ch04/Fold.hs myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl f z xs = foldr step id xs z where step x g a = g (f a x) 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? (Partial application? The order of execution?) Btw, is there a way I can observe the type signature of 'step' in this code? Thanks in advance! -- Pan, Xingzhi http://www.panxingzhi.net _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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. |
On Tue, Jan 26, 2010 at 11:24 PM, Eduard Sergeev
<[hidden email]> 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? > -- > View this message in context: http://old.nabble.com/foldl-in-terms-of-foldr-tp27322307p27324376.html > Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Pan, Xingzhi http://www.panxingzhi.net _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Xingzhi Pan wrote:
> On Tue, Jan 26, 2010 at 11:24 PM, Eduard Sergeev > <[hidden email]> 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? > -> 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. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Xingzhi Pan
Am Dienstag 26 Januar 2010 16:44:11 schrieb Xingzhi Pan:
> On Tue, Jan 26, 2010 at 11:24 PM, Eduard Sergeev > > <[hidden email]> 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? > No, typo by Eduard, step :: b -> (a -> c) -> (a -> c). foldr :: (t -> u -> u) -> u -> [t] -> u , so t === b, u === a -> c Now, in "foldr step id xs", id has type u === a -> c, hence c === a. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Neil Brown-7
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 |
In reply to this post by Neil Brown-7
On Tue, Jan 26, 2010 at 11:51 PM, Neil Brown <[hidden email]> wrote:
> Xingzhi Pan wrote: >> >> On Tue, Jan 26, 2010 at 11:24 PM, Eduard Sergeev >> <[hidden email]> 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Eduard Sergeev
On Wed, Jan 27, 2010 at 12:05 AM, Eduard Sergeev
<[hidden email]> wrote: > > > 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) I am not very sure about this. This rewriting was my first reaction against the original code but it failed compilation with GHC. More over, does "foldr step f id xs z" equal to "foldr (step f) id xs z"?? Thanks! > > 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. > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Pan, Xingzhi http://www.panxingzhi.net _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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). |
Correction :) 4-arg and 3-arg respectively. |
In reply to this post by Xingzhi Pan
On Tue, 26 Jan 2010, Xingzhi Pan wrote: > Hi, > > I am reading Real World Haskell and have some questions about the > piece of code implementing foldl in terms of foldr: > > -- file: ch04/Fold.hs > myFoldl :: (a -> b -> a) -> a -> [b] -> a > myFoldl f z xs = foldr step id xs z > where step x g a = g (f a x) > > 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? (Partial application? The order > of execution?) http://www.haskell.org/haskellwiki/Foldl_as_foldr > Btw, is there a way I can observe the type signature of 'step' in this code? http://www.haskell.org/haskellwiki/Determining_the_type_of_an_expression _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Xingzhi Pan
On Tue, Jan 26, 2010 at 5:04 AM, Xingzhi Pan <[hidden email]> wrote:
> myFoldl :: (a -> b -> a) -> a -> [b] -> a > myFoldl f z xs = foldr step id xs z > where step x g a = g (f a x) > > Btw, is there a way I can observe the type signature of 'step' in this code? Here is how I do it: Prelude> :t \[f] -> \x g a -> g (f a x) \[f] -> \x g a -> g (f a x) :: [t1 -> t -> t2] -> t -> (t2 -> t3) -> t1 -> t3 The [] are unnecessary but help me differentiate the "givens" from the actual arguments to the function. Here's a way that gives better type variables and properly constrains the type of f: Prelude> let test [f] x g a = g (f a x) where typeF = f `asTypeOf` const Prelude> :t test test :: [a -> b -> a] -> b -> (a -> t) -> a -> t -- ryan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Tue, Jan 26, 2010 at 1:56 PM, Ryan Ingram <[hidden email]> wrote:
> On Tue, Jan 26, 2010 at 5:04 AM, Xingzhi Pan <[hidden email]> wrote: >> myFoldl :: (a -> b -> a) -> a -> [b] -> a >> myFoldl f z xs = foldr step id xs z >> where step x g a = g (f a x) >> >> Btw, is there a way I can observe the type signature of 'step' in this code? > > Here is how I do it: > > Prelude> :t \[f] -> \x g a -> g (f a x) > \[f] -> \x g a -> g (f a x) > :: [t1 -> t -> t2] -> t -> (t2 -> t3) -> t1 -> t3 > > The [] are unnecessary but help me differentiate the "givens" from the > actual arguments to the function. > This is the only thing I use -XImplicitParams for: {--} :t \x g a -> g (?f a x) \x g a -> g (?f a x) :: (?f::t -> t1 -> t2) => t1 -> (t2 -> t3) -> t -> t3 Which differentiates the givens and gives them names :-) Luke _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Xingzhi Pan
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 [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
> 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 > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe > > _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
> f :: a -> b -> c is a function that takes an a, a b, and returns a c. > 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? The types are isomorphic. They both have the same extension. Both types are empty. How do you make a function that returns an ununtyped value? You can't. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |