foldl in terms of foldr

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

foldl in terms of foldr

Xingzhi Pan
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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Eduard Sergeev
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.
Reply | Threaded
Open this post in threaded view
|

foldl in terms of foldr

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?

> --
> 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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Neil Brown-7
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.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Daniel Fischer-4
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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Eduard Sergeev
In reply to this post by Neil Brown-7
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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Xingzhi Pan
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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Xingzhi Pan
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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Eduard Sergeev
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).
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Eduard Sergeev
Eduard Sergeev wrote
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.
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Henning Thielemann
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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Ryan Ingram
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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Luke Palmer-2
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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Alexander Solla-2
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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Dan Weston

 > 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
Reply | Threaded
Open this post in threaded view
|

Re: foldl in terms of foldr

Alexander Solla-2

 > 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