+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 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Thank you for replying! It becomes a lot clearer now. :-) On Sat, Aug 8, 2020, 14:25 Bob Ippolito 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 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

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

On Fri, Aug 7, 2020 at 9:12 PM Austin Zhu 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-- -- Kim-Ee

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners