codemachine

Type Tetris

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

1
fmap sum $ Just [1, 2, 3]

So does this one:

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

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

First consider fmap . fmap:

1
2
3
4
5
6
7
8
9
10
11
(.) :: (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:

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

Now apply fmap . fmap to sum:

1
2
3
4
5
(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:

1
Just :: a -> Maybe a

can also be expressed as:

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

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

Consider the signature of (fmap . fmap) sum.

1
2
3
4
...
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

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

We can further specialize it by replacing f with Maybe.

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

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

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

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

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

which can be rewritten idiomatically as:

1
    ... => t b -> Maybe b

This leaves us with:

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

Comments