How (fmap . fmap) typechecks

Question

I have been going through a article(http://comonad.com/reader/2012/abstracting-with-applicatives/) and found the following snippet of code there:

newtype Compose f g a = Compose (f (g a)) deriving Show

instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose $ (fmap . fmap) f x

How does actually (fmap . fmap) typechecks ?

Their types being:

(.)  :: (a -> b) -> (r -> a) -> (r -> b)
fmap :: (a -> b) -> f a -> f b
fmap :: (a -> b) -> f a -> f b

Now from here I can see in no way in which fmap . fmap will typecheck ?

Answer 1

First let's change the type variables' names to be unique:

(.)  :: (a -> b) -> (r -> a) -> (r -> b)
fmap :: Functor f => (c -> d) -> f c -> f d
fmap :: Functor g => (x -> y) -> g x -> g y

Now the first parameter to . has type a -> b and we supply an argument of type (c -> d) -> (f c -> f d), so a is c -> d and b is f c -> f d. So so far we have:

(.) :: Functor f => -- Left operand
                    ((c -> d) -> (f c -> f d)) ->
                    -- Right operand
                    (r -> (c -> d)) ->
                    -- Result
                    (r -> (f c -> f d))

The second parameter to . has type r -> a a.k.a. r -> (c -> d) and the argument we give has type (x -> y) -> (g x -> g y), so r becomes x -> y, c becomes g x and d becomes g y. So now we have:

(.)       :: (Functor f, Functor g) => -- Left operand
                                       ((g x -> g y) -> (f (g x) -> f (g y))) -> 
                                       -- Right operand
                                       ((x -> y) -> (g x -> g y)) ->
                                       -- Result
                                       (x -> y) -> f (g x) -> f (g y)
fmap.fmap :: (Functor f, Functor g) => (x -> y) -> f (g x) -> f (g y)

Answer 2

The expression fmap . fmap has two instances of fmap which can, in principle, have different types. So let's say their types are

fmap :: (x -> y) -> (g x -> g y)
fmap :: (u -> v) -> (f u -> f v)

Our job is to unify types (which amounts to coming up with equality relations between these type variables) so that the right-hand side of the first fmap is the same as the left-hand side of the second fmap. Hopefully you can see that if you set u = g x and v = g y you will end up with

fmap :: (  x ->   y) -> (   g x  ->    g y )
fmap :: (g x -> g y) -> (f (g x) -> f (g y))

Now the type of compose is

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

To make this work out, you can pick a = x -> y and b = g x -> g y and c = f (g x) -> f (g y) so that the type can be written

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

which is pretty unwieldy, but it's just a specialization of the original type signature for (.). Now you can check that everything matches up such that fmap . fmap typechecks.

---

An alternative is to approach it from the opposite direction. Let's say that you have some object that has two levels of functoriality, for example

>> let x = [Just "Alice", Nothing, Just "Bob"]

and you have some function that adds bangs to any string

bang :: String -> String
bang str = str ++ "!"

You'd like to add the bang to each of the strings in x. You can go from String -> String to Maybe String -> Maybe String with one level of fmap

fmap bang :: Maybe String -> Maybe String

and you can go to [Maybe String] -> [Maybe String] with another application of fmap

fmap (fmap bang) :: [Maybe String] -> [Maybe String]

Does that do what we want?

>> fmap (fmap bang) x
[Just "Alice!", Nothing, Just "Bob!"]

Let's write a utility function, fmap2, that takes any function f and applies fmap to it twice, so that we could just write fmap2 bang x instead. That would look like this

fmap2 f x = fmap (fmap f) x

You can certainly drop the x from both sides

fmap2 f = fmap (fmap f)

Now you realize that the pattern g (h x) is the same as (g . h) x so you can write

fmap2 f = (fmap . fmap) f

so you can now drop the f from both sides

fmap2 = fmap . fmap

which is the function you were interested in. So you see that fmap . fmap just takes a function, and applies fmap to it twice, so that it can be lifted through two levels of functoriality.

Answer 3

Old question, but to me, conceptually, fmap represents "taking an a -> b and bringing it 'one level up', to f a -> f b".

So if I had an a -> b, I can fmap it to give me an f a -> f b.

If I had an f a -> f b, I can fmap it again to give me a g (f a) -> g (f a). Lift that f a -> f b function to new heights --- a new level.

So "fmapping" once lifts the function once. fmapping twice lifts that lifted function...so, a double lift.

Put in the language of haskell syntax:

f                    ::         a   ->         b
fmap f               ::       f a   ->       f b
fmap (fmap f)        ::    g (f a)  ->    g (f b)
fmap (fmap (fmap f)) :: h (g (f a)) -> h (g (f b))

Notice how each successive fmap lifts the original a -> b to another new level. So,

fmap               :: (a -> b) -> (      f a  ->        f b  )
fmap . fmap        :: (a -> b) -> (   g (f a) ->     g (f b) )
fmap . fmap . fmap :: (a -> b) -> (h (g (f a)) -> h (g (f a)))

Any "higher order function" that returns a function of the same arity as its input can do this. Take zipWith :: (a -> b -> c) -> ([a] -> [b] -> [c]), which takes a function taking two arguments and returns a new function taking two arguments. We can chain zipWiths the same way:

f                   ::   a   ->   b   ->   c
zipWith f           ::  [a]  ->  [b]  ->  [c]
zipWith (zipWith f) :: [[a]] -> [[b]] -> [[c]]

So

zipWith           :: (a -> b -> c) -> ( [a]  ->  [b]  ->  [c] )
zipWith . zipWith :: (a -> b -> c) -> ([[a]] -> [[b]] -> [[c]])

liftA2 works pretty much the same way:

f                 ::      a  ->      b  ->      c
liftA2 f          ::    f a  ->    f b  ->    f c
liftA2 (liftA2 f) :: g (f a) -> g (f b) -> g (f c)

One rather surprising example that is put to great use in the modern implementation of the lens library is traverse:

f                                ::         a   -> IO          b
traverse f                       ::       f a   -> IO (      f b  )
traverse (traverse f)            ::    g (f a)  -> IO (   g (f b) )
traverse (traverse (traverse f)) :: h (g (f a)) -> IO (h (g (f b)))

So you can have things like:

traverse            :: (a -> m b) -> (   f a  -> m (   f b ))
traverse . traverse :: (a -> m b) -> (g (f a) -> m (g (f b)))