<div dir="ltr">I think the part that is confusing is that there are two steps here, there is the <b>foldr</b>, and then there is the application of <b>id</b> to the result of the <b>foldr</b>. <b>foldr</b> is of type <b>(a -> b -> b) -> b -> [a] -> b</b>, and in your example the type for <b>a</b> is <b>Integer</b> (probably not precisely Integer, but let's just say it is for simplicity) and the type for <b>b</b> is <b>[Integer] -> [Integer]</b>. It would be better to think of it as <b>(foldr f (const []) xs) id</b>. Another way to think of it is that <b>foldr</b> replaces the list <b>:</b> constructor with the function (<b>f</b>) and the <b>[]</b> constructor with the given <b>b</b> (<b>id</b>). 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.<div><br></div><div><b>init' [1, 2, 3]</b></div><div><b>(foldr f (const []) (1 : 2 : 3 : [])) id</b></div><div><b>(1 `f` (2 `f` (3 `f` const []))) id</b></div><div><b>id ((2 `f` (3 `f` const [])) (1:))</b></div><div><b>(2 `f` (3 `f` const [])) (1:)<br></b></div><div>1 :<b> ((3 `f` const []) (2:))</b></div><div>1 : 2 :<b> (const [] (3:))</b></div><div>1 : 2 : []</div><div><b><br></b></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Aug 7, 2020 at 7:12 AM Austin Zhu <<a href="mailto:austinzhu666@gmail.com">austinzhu666@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);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">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>