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/cgibin/mailman/listinfo/beginners 
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 nonstrict 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:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
+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 nonstrict > 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/cgibin/mailman/listinfo/beginners > > > _______________________________________________ > Beginners mailing list > [hidden email] > http://mail.haskell.org/cgibin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
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/cgibin/mailman/listinfo/beginners 
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:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
Administrator

In reply to this post by Austin Zhu
On Fri, Aug 7, 2020 at 9:12 PM Austin Zhu <[hidden email]> wrote:
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 etaexpansion: 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.
 KimEe
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
+1
Il 10 agosto 2020 alle 08:00 KimEe 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 etaexpansion: 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/cgibin/mailman/listinfo/beginners > > >  >  KimEe > _______________________________________________ > Beginners mailing list > [hidden email] > http://mail.haskell.org/cgibin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
Free forum by Nabble  Edit this page 