How does composing with id change type

Question

If the type of foldr is

> :t foldr
forall a b. (a -> b -> b) -> b -> [a] -> b

and

> :t id
forall a. a -> a

then I would expect foldr (.) id to have the same type as foldr, rather than

> :t foldr (.) id
forall b. [b -> b] -> b -> b

It appears I'm mistaken about how composition works, because I had thought that for a function f that f . id would give f(id(x)) == f(x), preserving the type of f. What am I misunderstanding that would clarify the meaning of foldr (.) id and composition more generally?

Answer 1

This is not composition with id, as you'd get from foldr . id (notice the absence of parens). That would indeed be equivalent to foldr alone, perhaps the most important equivalency in category theory and thus also fundamental to Haskell.

Instead, what you've done there is, passed both (.) and id as arguments to foldr: putting . in parens makes it just another expression so ordinary Haskell function parsing applies, i.e. greedily use consecutive terms as arguments to the first one. You're lucky that this makes for a good type at all, for instance succ (.) id would have given the ridiculous signature Enum ((c -> c) -> (a -> c) -> a -> c) => (a -> c) -> a -> c.

How exactly it works with foldr can be seen by writing

 (.) :: (y->z) -> (x->y) -> (x->z)

unify (x->y) = (x->z) as in foldr's argument, i.e. y = z,

 (.) :: (y->y) -> (x->y) -> (x->y)

 foldr (.) :: (x->y) -> [y->y] -> (x->y)

Then id also requires x = y,

 foldr (.) id :: [x->x] -> (x->x)

Answer 2

You are not composing foldr with id. That would be foldr . id. What you are actually doing is applying foldr to (.), and then applying the result of such application to id.