How does this implementation of `init` work?

Question

I'm learning Haskell and I found an interesting implementation of init using foldr. However, I have difficulty understanding how it works.

init' xs = foldr f (const []) xs id
    where f x g h = h $ g (x:)

Consider I have an 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 find it 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 about 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.

Answer 1

For a list [1,2,3], the init' is substituted by:

init' [1,2,3]
  = foldr f (const []) [1,2,3] id
  = f 1 (foldr f (const []) [2,3]) id

Here f is thus called with 1 as x, foldr f (const []) [2,3] as g and id h, this thus means that the this is resolved to:

id (foldr f (const []) [2,3] (1:))

It thus means that instead of using id in the recursion, we now will prepend 1: to the result. Next we can resolve the inner foldr to:

foldr f (const []) [2,3] (1:)
 = f 2 (foldr f (const []) [3]) (1:)
 = (1:) (foldr f (const []) [3] (2:))

The inner foldr then results in:

foldr f (const []) [3] (2:)
 = f 3 (foldr f (const []) []) (2:)
 = (2:) (foldr f (const []) [] (3:))

finally the foldr f (const []) [] will resulve to const [].

This thus means that:

foldr f (const []) [3] (2:)
 = f 3 (foldr f (const []) []) (2:)
 = (2:) (foldr f (const []) [] (3:))
 = (2:) (const [] (3:))

The const will thus ignore the argument (3:), and return an empty list. So the result of foldr f (const []) [3] (2:) is [2]:

foldr f (const []) [3] (2:)
 = f 3 (foldr f (const []) []) (2:)
 = (2:) (foldr f (const []) [] (3:))
 = (2:) (const [] (3:))
 = (2:) []
 = [2]

If we substitute this in the foldr f (const []) [2,3] (1:), we get:

foldr f (const []) [2,3] (1:)
 = f 2 (foldr f (const []) [3]) (1:)
 = (1:) (foldr f (const []) [3] (2:))
 = (1:) [2]
 = [1,2]

so that means that init' [1,2,3] will return [1,2].

This thus means that a

foldr f (const []) [x1, x2, …, xn] (x0:)

will be replaced by:

(x0:) (foldr f (const []) [x2, x3, …, xn] (x1:))

If the list gets exhausted, then it will replace:

foldr f (const []) [] (xn:)

with:

const [] (xn:)

so the last element will be ignored by the const function.