How does (fmap.fmap) sum Just [1,2,3] type check in Haskell?

Question

I do not understand how does this simple expression type check in Haskell

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

The type for composition of fmaps is:

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

so I expected f1 ~ List and f ~ Maybe, which implies that type of the function should be Integer -> b. But if type-check it in ghci, I get:

t (fmap.fmap) _ Just [1, 2, 3]

<interactive>:1:13: error:
    • Found hole: _ :: [Integer] -> b
      Where: ‘b’ is a rigid type variable bound by
               the inferred type of it :: Maybe b at <interactive>:1:1
    • In the first argument of ‘fmap . fmap’, namely ‘_’
      In the expression: (fmap . fmap) _ Just [1, 2, 3]

I see ghci deducing the type of the function to be [Integer] -> b. How is this possible?

Answer 1

There's no reason to expect f1 ~ [] and f ~ Maybe. Notice that you need Just :: f (f1 a). We know Just :: a -> Maybe a. Therefore, in reality, f ~ (->) a and f1 ~ Maybe. Then you have

fmap . fmap :: (a -> b) -> (a -> Maybe a) -> a -> Maybe b
--             ^^sum^^^    ^^^^^Just^^^^^    ^ [1, 2, 3]

Since we know that [1, 2, 3] :: a, we can deduce a ~ [Integer] now (defaulting the Numeric type to Integer).

fmap . fmap :: ([Integer] -> b) -> ([Integer] -> Maybe [Integer]) -> [Integer] -> Maybe b

Answer 2

For posterity, here’s a tip for how you can figure this kind of thing out in the future. You can ask the type of a subexpression in ghci using a wildcard (as long as you don’t have PartialTypeSignatures enabled).

:t ((fmap :: _) . (fmap :: _)) sum Just [1, 2, 3]

This tells you that the outer fmap is used at type (a1 -> b) -> ([a] -> a1) -> [a] -> b while the inner one is used at type (a1 -> b) -> Maybe a1 -> Maybe b. It should be clear that the inner fmap is simply acting on Maybe. The outer fmap looks more complicated at first glance, but it’s an instantiation of the type of (.), which is fmap in the function reader functor.

(.)  :: ( y -> z) -> (  x ->  y) ->   x -> z
fmap :: (a1 -> b) -> ([a] -> a1) -> [a] -> b

x ~ [a]
y ~ a1
z ~ b

The functor here is ([a] ->), spelled (->) [a] in real code because Haskell doesn’t allow operator sections at the type level.

That tells you that the outer one is (.), and from there you can inline the definitions step by step to see how this is evaluated.

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

To reduce noise and avoid having to juggle so many type variables to determine which are relevant, you can fix some of the types with type signatures, here Int instead of Num a => a.

:t ((fmap :: _) . (fmap :: _)) sum Just [1 :: Int, 2, 3]

This gives (a -> b) -> ([Int] -> a) -> [Int] -> b for the outer fmap in the (->) [Int] functor, and (a -> b) -> Maybe a -> Maybe b for the inner fmap in Maybe.

And just for fun, going the other way, you can also replace the (.) with an fmap!

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