Haskell fmap composition misunderstanding

Question

If I compose two fmaps

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

I get a function which applies a function to a value inside 2 nested leves of structure, f1 and f.

And I can use it—this works as I expected:

Prelude> (fmap.fmap) (+1) [[1,2]]
[[2,3]]

With inferred type as I expected (2 leves of structure around result)

Prelude> :t (fmap.fmap) (+1) [[1,2]]
(fmap.fmap) (+1) [[1,2]] :: Num b => [[b]]

The following does not work. I also expect this (because we can't apply sum to a single number):

Prelude> (fmap.fmap) sum [[1,2]]
<interactive>:39:2: error:
 • Could not deduce (Num (t0 b))
 from the context: (Num (t b), Num b, Foldable t)
 bound by the inferred type for ‘it’:
 (Num (t b), Num b, Foldable t) => [[b]]
 at <interactive>:39:2-24
 The type variable ‘t0’ is ambiguous
 • In the ambiguity check for the inferred type for ‘it’
 To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
 When checking the inferred type
 it :: forall (t :: * -> *) b.
 (Num (t b), Num b, Foldable t) =>
 [[b]]
Prelude> :t (fmap.fmap) sum [[1,2]]
(fmap.fmap) sum [[1,2]] :: (Num (t b), Num b, Foldable t) => [[b]]

BUT! If I change one level of structure to a Maybe type:

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

then it begins to work, but in my opinion breaking the type signature (fmap.fmap) :: (Functor f, Functor f1) => (a -> b) -> f1 (f a) -> f1 (f b) (because it applies the sum function inside the first level of structure, not the second as I expected).

I think problem in my undersanding how function application order evaluates here, because I find that with parentheses this works as expected inside two levels of structure with foldable list values (vs numbers in first exapmles):

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

But what happens here:

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

1. Why is the first level of stucture skipped?

2. What is the order of function applications here?

3. How does Haskell infer the final type?

    Prelude> :t (fmap.fmap) sum Just [1,2]
    (fmap.fmap) sum Just [1,2] :: Num t => Maybe t
   

Why Maybe t and not Maybe List t as I understand (fmap.fmap) must determine f1 (f b) two levels of structure not one?

• chepner: You are confusing (fmap.fmap) sum Just [1,2] with (fmap.fmap) sum (Just [1,2]), which would indeed fail for the same reason that (fmap.fmap) sum [[1,2]] fails.

Answer 1

Let's compute, pretending that numeric literals are Ints for the sake of simplicity.

(fmap.fmap) sum Just [1,2]
= fmap (fmap sum) Just [1,2]
 | | \ -- an additional argument applied to the result of fmap
 | \ -- the value with a type of the form f a with f Functor
 \ -- the function to fmap

Here, Just is a function [Int] -> Maybe [Int], so the first fmap operates on the functor f = (->) [Int], we have fmap = (.) because that's how it's defined in Functor ((->) [Int]).

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

Now, fmap f (Just x) = Just (f x) since that's how Functor Maybe is defined.

= Just (sum [1,2])
= Just 3

1. why first level of structure skipped?

It isn't. The first level is (->) [Int].

2. what is the order of function applications here?

The usual one. fmap.fmap is applied to sum. The result is applied to Just. The final result is applied to [1,2].

3. how does Haskell infer the final type?

It sees that Just is a "value wrapped inside the (->) [Int] functor", and uses that to instantiate the first fmap. The second fmap is instead used on the Maybe level since Just returns that.

Answer 2

What you have just discovered is that functions are themselves functors. That statement may sound a bit confusing, so let’s explore this a bit further. Let’s have a look at the function composition operator (.):

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

But now let’s rewrite the type signature slightly:

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

Here, I’ve behaved as if the function composition arrow were a normal infix operator, and could be placed in front of what look like its ‘type parameters’ (which in fact it can be). And now we notice something interesting — (.) looks almost exactly like fmap! See:

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

And in fact it’s possible to write a Functor instance for the partially applied function arrow (->) r (where ((->) r) a is the same as (r -> a)):

instance Functor ((->) r) where
 fmap = (.)
-- type signature here would be:
-- fmap :: (a -> b) -> ((->) r) a -> ((->) r) b
-- that is:
-- fmap :: (a -> b) -> (r -> a) -> (r -> b)

So, if f and g are functions, then fmap f g = f . g.

Now, how does that relate to your question? Let’s have a look at the expression you’re confused about:

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

Let’s go through this bit by bit. First, notice that this can be rewritten as: (fmap (fmap sum) Just) [1,2]. Now, fmap sum is a function — that means it’s a functor! So, using fmap = (.) for functions as I said above, this becomes: ((fmap sum) . Just) [1,2], that is fmap sum (Just [1,2]). And of course that simply evaluates to Just 3.

• dfeuer: Functions are not themselves functors. I know what you meant, but I think that statement is confusing.
• K. A. Buhr: Perhaps: What you have discovered is that a function type r -> a is also a functor in a, like Maybe a, and so is a "level of structure" for fmap to act on.
• bradrn: @dfeuer Why not? Last I checked there was a perfectly fine instance Functor ((->) r).
• dfeuer: The (endo)functor consists of a mapping (namely (->) r) from objects in Hask to objects in Hask, along with a mapping, fmap @((->) r), from morphisms (functions) to morphisms. We conventionally just talk about the object mapping. But the morphisms themselves are not functors.
• bradrn: @dfeuer So in that case, would it also be incorrect to say that ‘Maybe is a functor’, since the objects themselves are not functors? (Sorry if I’m misinterpreting what you’re saying — I’m not too good at category theory.)

Answer 3

Thanx for answers, it cleans for me that Just not Just [1,2] goes as second argument to (fmap.fmap).

I want to write type inference as I understand in more details (correct me if I wrong)

We have expression: (fmap.fmap) sum Just [1,2]

the type of (fmap.fmap) is (a -> b) -> f1 (f a) -> f1 (f b)

this determine that it takes two next arguments - sum and Just and return function.

sum has type List int -> int (for simplicity int) this implies that a = List int and b = int

Second argument Just has type a -> Maybe a or another words (->) a (Maybe a) so f1 = (->) a and f = Maybe

this implies that f1 (f b) = (->) (List int) (Maybe int)

Or another words the result type of expression (fmap.fmap) sum Just is List int -> Maybe int So the result is function.

And finnaly we apply value [1,2] to this function and get value Just 3 as expected with infered types.