<div>On Fri, Aug 7, 2020 at 9:12 PM Austin Zhu <<a href="mailto:austinzhu666@gmail.com">austinzhu666@gmail.com</a>> wrote:<br></div><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto">Hello!<div dir="auto"><br></div><div dir="auto">I'm learning Haskell and I found an interesting implementation of init using foldr. However I have difficulty understand how it works. </div><div dir="auto"><br></div><div dir="auto"><b>init' xs = foldr f (const []) xs id</b></div><div dir="auto"><b>    where f x g h = h $ g (x:)</b></div><div dir="auto"><br></div><div dir="auto">Consider I have a input of <b>[1,2,3]</b>, then is would become</div><div dir="auto"><br></div><div dir="auto"><b>f 1 (f 2 ( f 3 (const []))) id</b></div><div dir="auto"><br></div><div dir="auto">I substitute those parameters into f and the innermost one becomes <b>h $ (const []) (1:)</b>, which is simply <b>h []</b>. However when I want to reduce the expression further, I found it's hard to grasp. The next one becomes <b>f 2 (h [])</b> , which is</div><div dir="auto"><br></div><div dir="auto"><b>h $ (h []) (2:)</b></div><div dir="auto"><br></div><div dir="auto"></div></div></blockquote><div dir="auto"><br></div><div dir="auto">The last line isn’t correct because of erroneous alpha capture.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">Try substituting that in </div><div dir="auto"><br></div><div dir="auto"><div dir="auto"><b>f 1 (f 2 ( f 3 (const []))) id</b></div><div dir="auto"><b><br></b></div></div><div dir="auto">to see what you get.</div><div dir="auto"><br></div><div dir="auto">Hint: Note how f 3 (const []) evaluates to</div><div dir="auto"><br></div><div dir="auto">\h -> h (const [] (3:))</div><div dir="auto">= \h -> h []</div><div dir="auto">= ($ [])</div><div dir="auto"><br></div><div dir="auto">Next f 2 ($ []) becomes</div><div dir="auto"><br></div><div dir="auto">\h -> h (($ []) (2:))</div><div dir="auto">= \h -> h (2:[])</div><div dir="auto">= ($ (2:[]))</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div dir="auto">if it works like that. This looks confusing to me. To match the type of <b>foldr</b>, h should be of type <b>[a] -> [a]</b> and <b>h []</b> would just be of type <b>[a]</b>, which isn't applicable to <b>(2:)</b>.</div><div dir="auto"><br></div><div dir="auto">I also thought it in another way that <b>f x g</b> returns a function of type <b>([a] -> [a]) -> [a],</b> this kinda makes sense considering applying <b>id</b> afterwards. But then I realized I still don't know what this <b>h</b> is doing here. It looks like <b>h</b> conveys <b>g (x:)</b> from last time into the next application.</div><div dir="auto">Did I miss something when I think about doing fold with function as accumulator?<br></div><div dir="auto"><br></div><div dir="auto">I'd really appreciate if anyone could help me with this.</div></div>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature">-- Kim-Ee</div>