How can fmap be used with a data constructor?

Question

I'm trying to understand some haskell code.

This makes sense.

Prelude> fmap (+1) (Just 1)
Just 2

This also makes sense.

Prelude> (fmap.fmap) (+1) (Just [1])
Just [2]

But I don't understand how this works.

Prelude> (fmap.fmap) (+1) Just 1
Just 2

I've tried working the parts out. It seems to me that this is what's happening.

(fmap (fmap (+1)) Just) 1

I tried typing the subexpressions.

This makes sense.

Prelude> :t fmap (+1)
fmap (+1) :: (Functor f, Num b) => f b -> f b

This still makes sense.

Prelude> :t fmap (fmap (+1))
fmap (fmap (+1)) :: (Functor f, Functor f1, Num b) =>
    f (f1 b) -> f (f1 b)

But I don't understand this.

Prelude> :t fmap (fmap (+1)) Just
fmap (fmap (+1)) Just :: Num b => b -> Maybe b

How did a function with type

(Functor f, Functor f1, Num b) => f (f1 b) -> f (f1 b)

after applying Just which has type:

a -> Maybe a

result in this type?

Num b => b -> Maybe b

The question confused about function as instance of Functor in haskell might have something to do with this, but I still am confused.

Answer 1

What happened was f resolved to the functor (->) a, and f1 to Maybe, since

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

So if we write the type of fmap (fmap (+1)) with the above bindings we get:

fmap (fmap (+1)) :: Num b => (->) a (Maybe b) -> (->) a (Maybe b)

Rewriting (->) as an infix constructor we get:

fmap (fmap (+1)) :: Num b => (a -> Maybe b) -> (a -> Maybe b)

Now we apply this to Just :: a -> Maybe a so we get

fmap (fmap (+1)) Just :: Num a => a -> Maybe a

Answer 2

You write Just 1 instead of (Just 1) so as a result, these are two separate parameters. We can now rewrite it in a more canonical form, like:

   (fmap . fmap) (+1) Just 1
-> (\x -> fmap (fmap x)) (+1) Just 1
-> ((fmap (fmap (+1)) Just) 1

So now we can analyze the types:

fmap1 :: Functor f => (a -> b) -> f a -> f b
fmap2 :: Functor g => (c -> d) -> g c -> g d
(+1) :: Num h => h -> h
Just :: i -> Maybe i
1 :: Num j => j

Where fmapi is the i-th fmap in the expression (if we read it left-to-right). If we know perform some analysis, we see that since we use fmap (+1), we know that c ~ d ~ h:

fmap1 :: Functor f => (a -> b) -> f a -> f b
fmap2 :: Functor g => (h -> h) -> g h -> g h
(+1) :: Num h => h -> h
Just :: i -> Maybe i
1 :: Num j => j

We then see that the first fmap (fmap1) is called with fmap (+1) :: Functor g => g h -> g h as first argument, and Just :: i -> Maybe i as second argument. So if we further perform type analysis we get: (a -> b) ~ g h -> g h, so a ~ b ~ g h, and we know that f (g h) ~ i -> Maybe i, so that means that f (g h) ~ (->) i (Maybe i) so f ~ (->) i and g ~ Maybe, h ~ i, furthermore i ~ j:

fmap1 :: (Maybe i -> Maybe i) -> (->) i (Maybe i) -> (->) i Maybe i
fmap2 :: (i -> i) -> Maybe i -> Maybe i
(+1) :: Num h => i -> i
Just :: i -> Maybe i
1 :: Num i => i

Now a crucial aspect here is that (->) r is a functor as well, indeed in the base-4.10.1.0 source code we see:

instance Functor ((->) r) where
    fmap = (.)

We can here see a function as a functor, and if we perform an fmap we "post process" the result. So it means that after we apply Just, we apply fmap (+1) to that result. So the first fmap is equivalent to (.) whereas the second one is the fmap over Maybe, so as a result we get:

   ((fmap (fmap (+1)) Just) 1
-> (((.) (fmap (+1)) Just) 1
-> ((\x -> (fmap (+1) (Just x)) 1
-> fmap (+1) (Just 1)
-> Just 2

So in short we use the (fmap (+1)) as a post processing step, after we apply Just to 1.