Understanding functions like f a b c = c $ b a

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

Understanding functions like f a b c = c $ b a

Austin Zhu
Hello!

I'm learning Haskell and I found an interesting implementation of init using foldr. However I have difficulty understand how it works. 

init' xs = foldr f (const []) xs id
    where f x g h = h $ g (x:)

Consider I have a input of [1,2,3], then is would become

f 1 (f 2 ( f 3 (const []))) id

I substitute those parameters into f and the innermost one becomes h $ (const []) (1:), which is simply h []. However when I want to reduce the expression further, I found it's hard to grasp. The next one becomes f 2 (h []) , which is

h $ (h []) (2:)

if it works like that. This looks confusing to me. To match the type of foldr, h should be of type [a] -> [a] and h [] would just be of type [a], which isn't applicable to (2:).

I also thought it in another way that f x g returns a function of type ([a] -> [a]) -> [a], this kinda makes sense considering applying id afterwards. But then I realized I still don't know what this h is doing here. It looks like h conveys g (x:) from last time into the next application.
Did I miss something when I think about doing fold with function as accumulator?

I'd really appreciate if anyone could help me with this.

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Understanding functions like f a b c = c $ b a

Bob Ippolito
I think the part that is confusing is that there are two steps here, there is the foldr, and then there is the application of id to the result of the foldr. foldr is of type (a -> b -> b) -> b -> [a] -> b, and in your example the type for a is Integer (probably not precisely Integer, but let's just say it is for simplicity) and the type for b is [Integer] -> [Integer]. It would be better to think of it as (foldr f (const []) xs) id. Another way to think of it is that foldr replaces the list : constructor with the function (f) and the [] constructor with the given b (id). Here's how I would think about the computation. In Haskell it's usually best to start with the outside and work in, due to the non-strict evaluation. At the end I've removed the bold from the terms that are already completely reduced.

init' [1, 2, 3]
(foldr f (const []) (1 : 2 : 3 : [])) id
(1 `f` (2 `f` (3 `f` const []))) id
id ((2 `f` (3 `f` const [])) (1:))
(2 `f` (3 `f` const [])) (1:)
1 : ((3 `f` const []) (2:))
1 : 2 : (const [] (3:))
1 : 2 : []


On Fri, Aug 7, 2020 at 7:12 AM Austin Zhu <[hidden email]> wrote:
Hello!

I'm learning Haskell and I found an interesting implementation of init using foldr. However I have difficulty understand how it works. 

init' xs = foldr f (const []) xs id
    where f x g h = h $ g (x:)

Consider I have a input of [1,2,3], then is would become

f 1 (f 2 ( f 3 (const []))) id

I substitute those parameters into f and the innermost one becomes h $ (const []) (1:), which is simply h []. However when I want to reduce the expression further, I found it's hard to grasp. The next one becomes f 2 (h []) , which is

h $ (h []) (2:)

if it works like that. This looks confusing to me. To match the type of foldr, h should be of type [a] -> [a] and h [] would just be of type [a], which isn't applicable to (2:).

I also thought it in another way that f x g returns a function of type ([a] -> [a]) -> [a], this kinda makes sense considering applying id afterwards. But then I realized I still don't know what this h is doing here. It looks like h conveys g (x:) from last time into the next application.
Did I miss something when I think about doing fold with function as accumulator?

I'd really appreciate if anyone could help me with this.
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Understanding functions like f a b c = c $ b a

Francesco Ariis
+1

Il 07 agosto 2020 alle 22:24 Bob Ippolito ha scritto:

> I think the part that is confusing is that there are two steps here, there
> is the *foldr*, and then there is the application of *id* to the result of
> the *foldr*. *foldr* is of type *(a -> b -> b) -> b -> [a] -> b*, and in
> your example the type for *a* is *Integer* (probably not precisely Integer,
> but let's just say it is for simplicity) and the type for *b* is *[Integer]
> -> [Integer]*. It would be better to think of it as *(foldr f (const [])
> xs) id*. Another way to think of it is that *foldr* replaces the list *:*
> constructor with the function (*f*) and the *[]* constructor with the given
> *b* (*id*). Here's how I would think about the computation. In Haskell it's
> usually best to start with the outside and work in, due to the non-strict
> evaluation. At the end I've removed the bold from the terms that are
> already completely reduced.
>
> *init' [1, 2, 3]*
> *(foldr f (const []) (1 : 2 : 3 : [])) id*
> *(1 `f` (2 `f` (3 `f` const []))) id*
> *id ((2 `f` (3 `f` const [])) (1:))*
>
> *(2 `f` (3 `f` const [])) (1:)*
> 1 :* ((3 `f` const []) (2:))*
> 1 : 2 :* (const [] (3:))*
> 1 : 2 : []
>
>
> On Fri, Aug 7, 2020 at 7:12 AM Austin Zhu <[hidden email]> wrote:
>
> > Hello!
> >
> > I'm learning Haskell and I found an interesting implementation of init
> > using foldr. However I have difficulty understand how it works.
> >
> > *init' xs = foldr f (const []) xs id*
> > *    where f x g h = h $ g (x:)*
> >
> > Consider I have a input of *[1,2,3]*, then is would become
> >
> > *f 1 (f 2 ( f 3 (const []))) id*
> >
> > I substitute those parameters into f and the innermost one becomes *h $
> > (const []) (1:)*, which is simply *h []*. However when I want to reduce
> > the expression further, I found it's hard to grasp. The next one becomes *f
> > 2 (h [])* , which is
> >
> > *h $ (h []) (2:)*
> >
> > if it works like that. This looks confusing to me. To match the type of
> > *foldr*, h should be of type *[a] -> [a]* and *h []* would just be of
> > type *[a]*, which isn't applicable to *(2:)*.
> >
> > I also thought it in another way that *f x g* returns a function of type *([a]
> > -> [a]) -> [a],* this kinda makes sense considering applying *id*
> > afterwards. But then I realized I still don't know what this *h* is doing
> > here. It looks like *h* conveys *g (x:)* from last time into the next
> > application.
> > Did I miss something when I think about doing fold with function as
> > accumulator?
> >
> > I'd really appreciate if anyone could help me with this.
> > _______________________________________________
> > Beginners mailing list
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> >

> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Understanding functions like f a b c = c $ b a

Francesco Ariis
Il 08 agosto 2020 alle 13:24 Francesco Ariis ha scritto:
> +1

This is silly me thinking I was replying to a Discourse thread liking
the post…
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Understanding functions like f a b c = c $ b a

Austin Zhu
In reply to this post by Bob Ippolito
Thank you for replying! It becomes a lot clearer now. :-)

On Sat, Aug 8, 2020, 14:25 Bob Ippolito <[hidden email]> wrote:
I think the part that is confusing is that there are two steps here, there is the foldr, and then there is the application of id to the result of the foldr. foldr is of type (a -> b -> b) -> b -> [a] -> b, and in your example the type for a is Integer (probably not precisely Integer, but let's just say it is for simplicity) and the type for b is [Integer] -> [Integer]. It would be better to think of it as (foldr f (const []) xs) id. Another way to think of it is that foldr replaces the list : constructor with the function (f) and the [] constructor with the given b (id). Here's how I would think about the computation. In Haskell it's usually best to start with the outside and work in, due to the non-strict evaluation. At the end I've removed the bold from the terms that are already completely reduced.

init' [1, 2, 3]
(foldr f (const []) (1 : 2 : 3 : [])) id
(1 `f` (2 `f` (3 `f` const []))) id
id ((2 `f` (3 `f` const [])) (1:))
(2 `f` (3 `f` const [])) (1:)
1 : ((3 `f` const []) (2:))
1 : 2 : (const [] (3:))
1 : 2 : []


On Fri, Aug 7, 2020 at 7:12 AM Austin Zhu <[hidden email]> wrote:
Hello!

I'm learning Haskell and I found an interesting implementation of init using foldr. However I have difficulty understand how it works. 

init' xs = foldr f (const []) xs id
    where f x g h = h $ g (x:)

Consider I have a input of [1,2,3], then is would become

f 1 (f 2 ( f 3 (const []))) id

I substitute those parameters into f and the innermost one becomes h $ (const []) (1:), which is simply h []. However when I want to reduce the expression further, I found it's hard to grasp. The next one becomes f 2 (h []) , which is

h $ (h []) (2:)

if it works like that. This looks confusing to me. To match the type of foldr, h should be of type [a] -> [a] and h [] would just be of type [a], which isn't applicable to (2:).

I also thought it in another way that f x g returns a function of type ([a] -> [a]) -> [a], this kinda makes sense considering applying id afterwards. But then I realized I still don't know what this h is doing here. It looks like h conveys g (x:) from last time into the next application.
Did I miss something when I think about doing fold with function as accumulator?

I'd really appreciate if anyone could help me with this.
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Understanding functions like f a b c = c $ b a

Kim-Ee Yeoh
Administrator
In reply to this post by Austin Zhu
On Fri, Aug 7, 2020 at 9:12 PM Austin Zhu <[hidden email]> wrote:
Hello!

I'm learning Haskell and I found an interesting implementation of init using foldr. However I have difficulty understand how it works. 

init' xs = foldr f (const []) xs id
    where f x g h = h $ g (x:)

Consider I have a input of [1,2,3], then is would become

f 1 (f 2 ( f 3 (const []))) id

I substitute those parameters into f and the innermost one becomes h $ (const []) (1:), which is simply h []. However when I want to reduce the expression further, I found it's hard to grasp. The next one becomes f 2 (h []) , which is

h $ (h []) (2:)


The last line isn’t correct because of erroneous alpha capture.

Modulo certain things that aren’t relevant here, the definition of the folding function f is equivalent to the eta-expansion: f x g = \h -> h (g (x:)). Note the lambda abstraction.

Try substituting that in 

f 1 (f 2 ( f 3 (const []))) id

to see what you get.

Hint: Note how f 3 (const []) evaluates to

\h -> h (const [] (3:))
= \h -> h []
= ($ [])

Next f 2 ($ []) becomes

\h -> h (($ []) (2:))
= \h -> h (2:[])
= ($ (2:[]))

And you can see how you end up with init’ [1,2,3] = 1:(2:[]) = [1,2]. Notice how I converted from a lambda abstraction to combinator form to prevent the named lambda variable h from obscuring what’s really going on.

Another way to figure out this out is by calculating the precise type of the folding function f that is provided to foldr and hence the type to h.


if it works like that. This looks confusing to me. To match the type of foldr, h should be of type [a] -> [a] and h [] would just be of type [a], which isn't applicable to (2:).

I also thought it in another way that f x g returns a function of type ([a] -> [a]) -> [a], this kinda makes sense considering applying id afterwards. But then I realized I still don't know what this h is doing here. It looks like h conveys g (x:) from last time into the next application.
Did I miss something when I think about doing fold with function as accumulator?

I'd really appreciate if anyone could help me with this.
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
--
-- Kim-Ee

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Understanding functions like f a b c = c $ b a

Francesco Ariis
+1

Il 10 agosto 2020 alle 08:00 Kim-Ee Yeoh ha scritto:

> On Fri, Aug 7, 2020 at 9:12 PM Austin Zhu <[hidden email]> wrote:
>
> > Hello!
> >
> > I'm learning Haskell and I found an interesting implementation of init
> > using foldr. However I have difficulty understand how it works.
> >
> > *init' xs = foldr f (const []) xs id*
> > *    where f x g h = h $ g (x:)*
> >
> > Consider I have a input of *[1,2,3]*, then is would become
> >
> > *f 1 (f 2 ( f 3 (const []))) id*
> >
> > I substitute those parameters into f and the innermost one becomes *h $
> > (const []) (1:)*, which is simply *h []*. However when I want to reduce
> > the expression further, I found it's hard to grasp. The next one becomes *f
> > 2 (h [])* , which is
> >
> > *h $ (h []) (2:)*
> >
> >
> The last line isn’t correct because of erroneous alpha capture.
>
> Modulo certain things that aren’t relevant here, the definition of the
> folding function f is equivalent to the eta-expansion: f x g = \h -> h (g
> (x:)). Note the lambda abstraction.
>
> Try substituting that in
>
> *f 1 (f 2 ( f 3 (const []))) id*
>
> to see what you get.
>
> Hint: Note how f 3 (const []) evaluates to
>
> \h -> h (const [] (3:))
> = \h -> h []
> = ($ [])
>
> Next f 2 ($ []) becomes
>
> \h -> h (($ []) (2:))
> = \h -> h (2:[])
> = ($ (2:[]))
>
> And you can see how you end up with init’ [1,2,3] = 1:(2:[]) = [1,2].
> Notice how I converted from a lambda abstraction to combinator form to
> prevent the named lambda variable h from obscuring what’s really going on.
>
> Another way to figure out this out is by calculating the precise type of
> the folding function f that is provided to foldr and hence the type to h.
>
>
> if it works like that. This looks confusing to me. To match the type of
> > *foldr*, h should be of type *[a] -> [a]* and *h []* would just be of
> > type *[a]*, which isn't applicable to *(2:)*.
> >
> > I also thought it in another way that *f x g* returns a function of type *([a]
> > -> [a]) -> [a],* this kinda makes sense considering applying *id*
> > afterwards. But then I realized I still don't know what this *h* is doing
> > here. It looks like *h* conveys *g (x:)* from last time into the next
> > application.
> > Did I miss something when I think about doing fold with function as
> > accumulator?
> >
> > I'd really appreciate if anyone could help me with this.
> > _______________________________________________
> > Beginners mailing list
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> >
> --
> -- Kim-Ee

> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners