Functor over multiple levels

Question

I have this lame attempt:

fmap2 :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap2 f f2 = (fmap2 f . fmap f2)

It is supposed to work like this:

fmap2 negate [[1,2], [3]] -- Returns [[-1,-2],[-3]]
fmap2 head [Just "abc",Nothing,Just "def"] -- Returns [Just 'a',Nothing,Just 'e']

Note, that this is an exercise. (I gave it a try for like 1,5 hours, yet did not found any solution.)

Q: What am I doing wrong there?

Answer 1

When you get stuck in something like this, I'd recommend using type holes as they drive you in the right direction

fmap2 :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap2 f nested_functor = fmap _something nested_functor 
--      |                |    |- notice this underscore
--      |                |- clearly we need to fmap something over the nested_functor but we don't know what yet
--      |- Using better names usually helps. Haskellers tend to use very short names, but that's not appropriate always

If you try to compile this code, ghc will notice the _something and will propose you a type for it

Found hole: _something :: g a -> g b <-- This is interesting
      Where: ‘a’, ‘g’, ‘b’ ... (blah blah blah, not interesting)
      Or perhaps ‘_something’ is mis-spelled, or not in scope

We know that _something needs to have type g a -> g b given Functor g. Hence:

fmap2 :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap2 f nested_functor = fmap something nested_functor
  where 
    -- remember something :: Functor g => g a -> g b
    something = undefined -- left as an exercise

Answer 2

You should fmap with a functor mapping as function for the inner structure, so something like:

fmap2 :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap2 f = fmap (fmap …)

where I leave filling in the … part as an exercise.

Answer 3

When used in this

fmap2 head [Just "abc",Nothing,Just "def"] -- Returns [Just 'a',Nothing,Just 'e']

• what type is head? It's [Char] -> Char¹;
• and what type is [Just "abc",Nothing,Just "def"]? It's [Maybe [Char]].

So you have a function [Char] -> Char and you want to apply it to the [Char]s that is inside a Maybe functor, that is in turn inside a [] functor.

One fmap allows you to go through one of those layers, so you need 2 to go through 2. Look:

           head  $       "abc"                     ==       'a'
      fmap head  $  Just "abc"                     ==  Just 'a'
      fmap head  $             Nothing             ==           Nothing
fmap (fmap head) $ [Just "abc",Nothing,Just "def"] == [Just 'a',Nothing,Just 'e']

---

Yes, head is a polymorphic [a] -> a, but in the case above it's operating on [Char].

Answer 4

import Test.QuickCheck

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

prop_negate :: Property
prop_negate = property (fmap2 negate [[1,2],[3]] == [[-1,-2],[-3]])

prop_head :: Property
prop_head = property (fmap2 head [Just "abc", Nothing, Just "def"]
                              == [Just 'a', Nothing, Just 'd'])

So let's look at the two versions side by side:

fmap2 :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap2 f f2 = (fmap2 f . fmap f2)

and

fmap2 :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap2 = fmap . fmap
-- or
fmap2 :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap2 fab fga = (fmap . fmap) fab fga

In the first version, you reference fmap2 within fmap2 making it recursive. I don't think you meant to do that. The nested functors are not a case of recursion, as the second test case makes clear with the Maybe functor inside a list functor -- definitely not a recursive repetition.

The next issue is with the two parameters given to fmap2. In the type signature the two parameters are correctly identified as 1) a function a -> b and 2) a nested functor, functor of type 'g' inside functor of type 'f'. Here the two parameters are very different -- a function to be applied to a nested functor and the nested functor itself. In the function binding (fmap2 f f2 = (fmap2 f . fmap2 f2)) it seems like the two parameters are supposed to be symmetrical -- taking the same place as a first parameter -- but as we just saw in the type signature they are two different things: a function and a functor, so clearly they cannot be used symmetrically. Either you are considering these two different things as two functions or two functors. I suspect you are thinking of the two functors (type f and type g). It seems like you are trying to fmap over the two nested functors separately here. As you will see, the two functors are supposed to be mapped over together.

The second version is written in two forms. In the first form, the "point-free" way of writing it, fmap2 is given simply as the composition of fmap twice. Since we want to apply a function a -> b to values of type 'a' inside two nested functors, the composition of fmap twice jumps over the first functor (type f) then the second functor (type g) to get to the value(s) of type 'a' and apply the transformation function.

In the second form of the second version, the parameters are explicitly given. (They are merely implied in the point-free version, which should be easy to see.) This should help to clarify the mistaken parameters in the first version. The transformation function fab and the nested functors fga play different roles. The double fmap digs down twice into fga to get to the values of type 'a' and apply the function fab (a -> b).

The structure of nested functors, the 'fg' part of fga, is thus preserved but the value(s) of type 'a' can be transformed into values of type 'b' (not necessarily different in the case of negate, but possibly so, as in the case of head which takes, in our example, a string and returns a character). In this way the function of type a -> b applied to the nested functors (f (g a)) will produce the same nested functors with (potentially) different values inside, (f (g b)) which is what the compiler expects from the type signature.