I think the part that is confusing is that there are two steps here, there is the
foldr, and then there is the application of
id to the result of the
foldr.
foldr is of type
(a -> b -> b) -> b -> [a] -> b, and in your example the type for
a is
Integer (probably not precisely Integer, but let's just say it is for simplicity) and the type for
b is
[Integer] -> [Integer]. It would be better to think of it as
(foldr f (const []) xs) id. Another way to think of it is that
foldr replaces the list
: constructor with the function (
f) and the
[] constructor with the given
b (
id). 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.
init' [1, 2, 3]
(foldr f (const []) (1 : 2 : 3 : [])) id
(1 `f` (2 `f` (3 `f` const []))) id
id ((2 `f` (3 `f` const [])) (1:))
(2 `f` (3 `f` const [])) (1:)
1 : ((3 `f` const []) (2:))
1 : 2 : (const [] (3:))
1 : 2 : []