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.
