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
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners