Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Understanding functions like f a b c = c $ b a (Kim-Ee Yeoh)
2. Re: Understanding functions like f a b c = c $ b a
(Francesco Ariis)
----------------------------------------------------------------------
Message: 1
Date: Mon, 10 Aug 2020 08:00:10 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>,
"[email protected]" <[email protected]>
Subject: Re: [Haskell-beginners] Understanding functions like f a b c
= c $ b a
Message-ID:
<CAPY+ZdSFmxPtT_ACtt-EtGSVmqoTuDgcfbLqJouSXMuR+FDN=w...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Fri, Aug 7, 2020 at 9:12 PM Austin Zhu <[email protected]> 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
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
--
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20200810/032dd823/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 10 Aug 2020 03:05:59 +0200
From: Francesco Ariis <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Understanding functions like f a b c
= c $ b a
Message-ID: <20200810010559.GA1732@extensa>
Content-Type: text/plain; charset=utf-8
+1
Il 10 agosto 2020 alle 08:00 Kim-Ee Yeoh ha scritto:
> On Fri, Aug 7, 2020 at 9:12 PM Austin Zhu <[email protected]> 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
> > [email protected]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> >
> --
> -- Kim-Ee
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 146, Issue 3
*****************************************
