The type of foldr (.) id

Question

I'm trying to figure out the type of the expression :

foldr (.) id 

GHCI gives me :

foldr (.) id :: Foldable t => t (b -> b) -> b -> b

And I can't figure this out. foldr type is Foldable t => (a -> b -> b) -> b -> t a -> b. So it takes 3 parameters as input. So i thought that foldr (.) id should take a single parameter as input. Can someone explain how to analyze the type of this expresion ?

Answer 1

The type Foldable t => t (b -> b) -> b -> b reads as:

• (Foldable t => ...) Choose any list-like "container" type t,
• (t (b -> b) -> ... ) then provide as an argument a t-container of functions b -> b,
• (b -> b) the final result will be a function b -> b.

So, it's only slightly more general than: "give me a list of functions, and I will produce a function".

Indeed, when we use lists as containers:

foldr (.) id [f1,f2,f3,...,fn]

results, by definition of foldr, in

f1 . (f2 . (f3 .  ... (fn . id) ...))

which is the composition of all the functions in the list.

So i thought that foldr (.) id should take a single parameter as input.

It does: the argument has type t (b -> b). Every function in Haskell takes a single parameter as input. E.g.

foo :: T -> U -> W -> Z

takes T and returns a function U -> W -> Z. Now, we can also say that foo takes two arguments of type T and U and returns a function W -> Z. Or That it takes three arguments T, U, and W, and returns a Z. There is no real difference between these interpretations of a type, thanks to currying, so we can pick the one which is the easiest to grasp.

In your case, the result type of foldr (.) id is b -> b, so one usually interprets the first b as an additional argument. This does not provide a good intuition, though. It's easier to think of b -> b being the result type.

---

More technically: the type of foldr is (renaming variables for clarity).

foldr :: Foldable t => (a -> c -> c) -> c -> t a -> c

In foldr (.) id, we can see that the type of the second argument is id :: b -> b, hence we are using c = (b -> b), as if we specialized the above type to:

foldr :: Foldable t => (a -> (b -> b) -> (b -> b)) -> (b -> b) -> t a -> (b -> b)

Now, the first argument must have type (.) :: (a -> (b -> b) -> (b -> b)) to type check. This is possible only if a = (b -> b). Hence, we specialize again.

foldr :: Foldable t => 
         ((b -> b) -> (b -> b) -> (b -> b)) ->
         (b -> b) -> 
         t (b -> b) ->
         (b -> b)

which is the final type: after this specialization, foldr can then be applied to (.) and id.

All the specializations above are inferred automatically by GHC from your code. Essentially, GHC chooses a and c in the only way that can make your code type check

Answer 2

TLDR answer:

foldr (.) id :: Foldable t => t (b -> b) -> b -> b

DOES take one argument. It takes a t (b -> b) and returns a b -> b.

This confusion is usually due to Haskell allowing the omission of parens in type signatures. Parens in types associate to the right. So another way to look at this:

foldr        :: Foldable t => (a -> r -> r) -> (r       -> (t  a       ->  r))
(.) :: (c -> d) -> (b -> c) -> (b -> d)
--        a     ->    r     ->    r
(.) :: (c -> c) -> (b -> c) -> (b -> c)
foldr (.)    :: Foldable t =>                  (b -> c) -> (t (c -> c) -> (b -> c))
id           ::                                 b -> b
foldr (.) id :: Foldable t =>                               t (b -> b) -> (b -> b)

You could

resultFun = foldr (.) id [(+1), (*4)]
resultFun 5
>>> 21

Or even

foldr (.) id [(+1), (*4)] 5
>>> 21