Search code examples
haskelltypesunification

Deriving the type of ((.) foldr)

I'm trying to manually derive the type of ((.) foldr)

(.) ::(b1 -> c1) -> (a1 -> b1) -> a1 -> c1
foldr :: (a2 -> b2 -> b2) -> b2 -> [a2] -> b2

Then:

b1 = a2 -> b2 -> b2
c1 = b2 -> [a2] -> b2

Matching the types I get:

((a2 -> b2 -> b2) -> (b2 -> [a2] -> b2)) -> (a1 -> (a2 -> b2 -> b2)) -> a1 -> (b2 -> [a2] -> b2)

But then I get confused on how to reduce this expresion.

Any help?

Thansks,
Sebastián.

Solution

  • Your correctly figured out the type of the (.) in (.) foldr. The (.) is applied to one argument (the foldr) so you can throw away the ((a2 -> b2 -> b2) -> (b2 -> [a2] -> b2)) and what remains is the type of (.) foldr:

    (a1 -> a2 -> b2 -> b2) -> a1 -> (b2 -> [a2] -> b2)

    Make sure that foldr can have type ((a2 -> b2 -> b2) -> (b2 -> [a2] -> b2)) before you throw it away. If you got the matching right, this check cannot fail, but it is a good sanity check.