What is the type of foldr map in haskell?

Question

I am trying to find out what the type of foldr map is, and how you should be solving something like this.

I know what the individual types are:

foldr :: (a -> b -> b) -> b -> [a] -> b
map :: (a -> b) -> [a] -> [b]

I know how the individual functions work, but finding out the type is something I just can't seem to solve.

foldr would take a function as first parameter, which would be the whole of map right?

All tips are welcome, I am new to Haskell and trying to learn puzzles like these.

Answer 1

As ingredients we have foldr and map. To avoid confusion, let us rename the a and b of map to c and d, since those are (possibly) different types. So we take as functions:

foldr :: (a -> b -> b) -> b -> [a] -> b
map   :: (c -> d) -> [c] -> [d]

or more verbose:

foldr :: (a -> (b -> b)) -> (b -> ([a] -> b))
map   :: (c -> d) -> ([c] -> [d])

Since map is the parameter of a function application with foldr as function, this means that the type of map should be the same as the type of the parameter of foldr, hence:

  a        -> (b   -> b)
~ (c -> d) -> ([c] -> [d])
----------------------------------
a ~ (c -> d), b ~ [c] ~ [d], c ~ d

So we have derived that a is the same type as c -> d, and that b is the same type as [c] and [d]. Therefore we also know that c ~ d (c is the same type as d).

The type of foldr map is the return type of the foldr function, but specialized with the equality relations we have derived, so:

foldr map :: b -> ([a] -> b)

so we replace a with c -> c, and b with [c], hence the type:

foldr map :: [c] -> ([c -> c] -> [c])

or in a less verbose form:

foldr map :: [c] -> [c -> c] -> [c]

Note: the signature of foldr has been generalized to foldr :: Foldable f => (a -> b -> b) -> b -> f a -> b, but deriving the type is similar.