Applying compose to fmap

Question

For weeks I've been trying to figure out how the Haskell compiler applies the (.) to fmap.

What I mean is.

:t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
:t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
:t (.) fmap
(.) fmap :: Functor f => (a -> a1 -> b) -> a -> f a1 -> f b

How did the compiler arrive at the type for (.) fmap?

I was actually going to ask this question here but while I was explaining what I've tried it all came together. So now I'm just going to post the answer too.

Answer 1

To get this I took fmap

fmap :: Functor f => (a -> b) -> f a -> f b
fmap :: Functor f => (a -> b) -> (f a -> f b)

if

:t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

then

(b -> c) of the start of the (.) function can be replaced with

((a -> b) -> (f a -> f b))

thus I have

((a1 -> b) -> (f a1 -> f b)) -> (a -> (a1 -> b)) -> a -> (f a1 -> f b)

Since (.) has been applied to fmap, we can eliminate ((a1 -> b) -> (f a1 -> f b)) and we are left with

(a -> (a1 -> b)) -> a -> (f a1 -> f b)

Then to be extra clean we can eliminate extra parentheses.

Glguy and Hamme from the IRC Beginner-haskell channel both reminded me (->) is right associative

e.g. (a -> b -> c -> d) = (a -> (b -> (c -> d)))

so we eliminate the redundant parentheses.

(a -> a1 -> b) -> a -> f a1 -> f b
:t (.) fmap
(.) fmap :: Functor f => (a -> a1 -> b) -> a -> f a1 -> f b

• Basu: I think you are missing an arrow there ((a1 -> b) -> (f a1 -> f b)) -> (a -> (a1 -> b)) -> a -> (f a1 -> f b)
• mac10688: I added the arrow. Thank you

Answer 2

The type signature can be understood intuitively if you rename a to c, rename a1 to a, and add an extra pair of parentheses:

> :t (.) fmap
(.) fmap :: Functor f => (c -> (a -> b)) -> c -> f a -> f b

The first argument is a function that returns another function (a -> b) that gets fed into fmap. Applying the first argument produces the fully composed function waiting on that one argument c. Applying c produces fmap (a -> b) which is only waiting on the last argument f a.

 ((.) fmap)
 ((.) fmap (c -> (a -> b)) -- Apply the 1st argument
 ((.) fmap (c -> (a -> b)) c -- Apply the 2nd argument
 fmap (a -> b)
 fmap (a -> b) f a -- Apply the 3rd argument
 f b -- The result

An example:

> ((.) fmap) (\n -> (+n)) 42 [1..5] -- Becomes: fmap (+42) [1..5]
[43,44,45,46,47]
> ((.) fmap) (\n -> (+n)) 13 [1..5]
[14,15,16,17,18]

Answer 3

One way to understand how the type is derived is to look at what (fmap .) means.

Consider fmap . g: what does this mean? Expanding the definition of ., we see that fmap . g = \x -> fmap (g x). Since the first argument to fmap needs to be a function with type a -> b, g must be function with a type like c -> a -> b; it computes an appropriate function given an argument.

Now, whereas we can apply fmap f directly to a list (or other functor), we need to give fmap . g an argument first:

fmap f someFunctorialValue == someOtherFunctorialValue
((fmap . g) x) someFunctorialValue == someOtherFunctorialValue

Dropping some redundant parentheses, this becomes

(fmap .) g x someFunctorialValue == someOtherFunctorialValue

and now we can directly what the type of each expression should be:

-- someFunctorialValue :: Functor f => f a
-- someOtherFunctorialValue :: Functor f => f b
-- x :: c
-- g :: (c -> a -> b)
-- (fmap .) :: (c -> a -> b) -> c -> f a -> f b
-- fmap :: ( a -> b) -> f a -> f b

In other words: fmap takes a concrete function a -> b, while (fmap .) takes a "parameterized" function g and a "function selector" x.