type tetris

Time for some Haskell. The following expression evaluates to Just 6:

fmap sum $ Just [1, 2, 3]

So does this one:

(fmap . fmap) sum Just $ [1, 2, 3]

How does the second one work? How do the type signatures line up?

First consider fmap . fmap:

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

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

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

fmap . fmap :: (Functor f, Functor f1) => (a -> b)
                                       -> f1 (f a)
                                       -> f1 (f b)

Then sum:

sum :: (Num a, Foldable t) => t a -> a

Now apply fmap . fmap to sum:

(fmap . fmap) sum :: (Num b,
                      Foldable t,
                      Functor f,
                      Functor f1) => f1 (f (t b))
                                  -> f1 (f b)

Next, the tricky bit. Note that (a -> b) ~ ((->) a b). So the signature of Just, which we’d usually write:

Just :: a -> Maybe a

can also be expressed as:

Just :: (->) a (Maybe a)

We want the type signature for (fmap . fmap) sum Just.

Consider the signature of (fmap . fmap) sum.

...
Functor f,
Functor f1) => f1 (f (t b))
            -> f1 (f b)

f1 must have a Functor instance.

((->) a) has a Functor instance for all a.

((->) (t b)), therefore, has a Functor instance.

If we replace f1 with ((->) (t b)), we produce a more specific type signature, expressing a specialization of (fmap . fmap) sum

        ... => ((->) (t b)) (f (t b))
            -> ((->) (t b)) (f b)

We can further specialize it by replacing f with Maybe.

        ... => ((->) (t b)) (Maybe (t b))
            -> ((->) (t b)) (Maybe b)

Now consider a specialization of Just where a ~ (t b)

Just :: (->) (t b) (Maybe (t b))

If we apply the specialized (fmap . fmap) sum to this specialization of Just, we get:

        ... => ((->) (t b)) (Maybe b)

which can be rewritten idiomatically as:

        ... => t b -> Maybe b

This leaves us with:

(fmap . fmap) sum Just :: (Num b, Foldable t) => t b -> Maybe b