Why is the functor implementation possible?

Question

I read following article https://www.schoolofhaskell.com/user/commercial/content/covariance-contravariance on the section Positive and negative position there is an example:

newtype Callback a = Callback ((a -> IO ()) -> IO ())

Is it covariant or contravariant on a?

Was the question.
The explanation is:

But now, we wrap up this entire function as the input to a new function, via: (a -> IO ()) -> IO (). As a whole, does this function consume an Int, or does it produce an Int? To get an intuition, let's look at an implementation of Callback Int for random numbers:

supplyRandom :: Callback Int
supplyRandom = Callback $ \f -> do
    int <- randomRIO (1, 10)
    f int

It's clear from this implementation that supplyRandom is, in fact, producing an Int. This is similar to Maybe, meaning we have a solid argument for this also being covariant. So let's go back to our positive/negative terminology and see if it explains why.

For me the function supplyRandom produces int <- randomRIO (1, 10) an Int and at the same time, it consumes the Int f int. I can not see, why the author mean, it only produces an Int.

An author continued further and explained the following:

In a -> IO (), a is in negative position. In (a -> IO ()) -> IO (), a -> IO () is in negative position. Now we just follow multiplication rules: when you multiply two negatives, you get a positive. As a result, in (a -> IO ())-> IO (), a is in the positive position, meaning that Callback is covariant on a, and we can define a Functor instance. And in fact, GHC agrees with us.

I understand the explanation but I didn't get the idea, why a is in the positive position and why it is covariant.

Consider the functor definition:

class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b

How it is possible to transform the type variable a in (a -> IO ())-> IO () to (b -> IO ())-> IO ()? I think, I misunderstand the concept.

Looking at the functor implementation:

newtype Callback a = Callback
    { runCallback :: (a -> IO ()) -> IO ()
    }

instance Functor Callback where
    fmap f (Callback g) = Callback $ \h -> g (h . f)

it is not clear where the transformation from a -> b takes place.

Answer 1

For me the function supplyRandom produces int <- randomRIO (1, 10) an Int and at the same time, it consumes the Int f int. I can not see, why the author mean, it only produces an Int.

Actually, in the line int <- randomRIO (1, 10) it's randomRIO that's producing the Int and it's supplyRandom that's consuming it. Similarly, in the line f int it's supplyRandom that's producing (i.e. supplying) the Int and it's f that's consuming it.

When we say producing and consuming we really just mean giving and taking. Producing doesn't necessarily mean producing out of thin air, although that's possible too. For example:

produceIntOutOfThinAir :: Callback Int
produceIntOutOfThinAir = Callback $ \f -> f 42 -- produced 42 out of thin air

In the author's example, supplyRandom doesn't produce an Int out of thin air. Instead, it takes the Int that randomRIO produces and in turn supplies that Int to f. That's perfectly fine.

The type signature of supplyRandom (i.e. (Int -> IO ()) -> IO () when unwrapped) only tells us that supplyRandom produces some Int. It doesn't specify how that Int must be produced.

---

Original answer:

Let's look at the type of fmap for Functor Callback:

fmap :: (a -> b) -> Callback a -> Callback b

Let's replace Callback with its unwrapped type:

                           Callback a                Callback b
                     __________|__________      _________|_________
                    |                     |    |                   |
fmap :: (a -> b) -> ((a -> IO ()) -> IO ()) -> (b -> IO ()) -> IO ()
        |______|    |_____________________|    |__________|
           |                   |                    |
           f                   g                    h

As you can see, fmap takes three inputs and needs to produce a value of type IO ():

f :: a -> b
g :: (a -> IO ()) -> IO ()
h :: b -> IO ()
--------------------------
IO ()

This is a visual representation of our goal. Everything above the line is our context (i.e. our hypotheses, or things we know). Everything below the line are our goals (i.e. things we're trying to prove using our hypotheses). In terms of Haskell code this can be written as:

fmap f g h = (undefined :: IO ()) -- goal 1

As you can see, we need to use the inputs f, g and h to produce a value of type IO (). Currently, I'm returning undefined. You can think of undefined as a placeholder for the actual value (i.e. a fill in the blank). So, how do we do fill in this blank? We have two options. We can either apply g or apply h since they both return an IO (). Suppose we decide to apply h:

fmap f g h = h (undefined :: b) -- goal 2

As you can see, h needs to be applied to a value of type b. Hence, our new goal is b. How do we fill in the new blank? The only function in our context which produces a value of type b is f:

fmap f g h = h (f (undefined :: a)) -- goal 3

However, we now have to produce a value of type a and we neither have a value of type a nor do we have any function which produces a value of type a. So, applying h is not an option. Back to goal 1. Our other option was to apply g. So, let's try that instead:

fmap f g h = g (undefined :: a -> IO ()) -- goal 4

Our new goal is a -> IO (). What does a value of type a -> IO () look like? Since it's a function we know that it looks like a lambda:

fmap f g h = g (\x -> (undefined :: IO ())) -- goal 5

Our new goal is again IO (). Seems like we're back to square 1, but wait... something is different. Our context is different because we introduced a new value x :: a:

f :: a -> b
g :: (a -> IO ()) -> IO ()
h :: b -> IO ()
x :: a
--------------------------
IO ()

Where did this value x come from? Seems like we just pulled it out of thin air right? No, we didn't pull it out of thin air. The value x came from g. You see, the type a is covariant in g which means that g produces a. Indeed, when we created the lambda to fill in the blank of goal 4 we introduced a new variable x into our context which gets its value, whatever it may be, from g.

Anyway, we again need to produce a value of type IO () but now we can go back to option 1 (i.e. apply h) because we finally have a value of type a. We don't want to go back to option 2 (i.e. apply g) because then we'd just be running in circles. Option 1 is our way out:

fmap f g h = g (\x -> h (undefined :: b)) -- goal 6

fmap f g h = g (\x -> h (f (undefined :: a))) -- goal 7

fmap f g h = g (\x -> h (f x)) -- goal proved

As you can see, \x -> h (f x) is just h . f (i.e. function composition) and the rest is packing and unpacking of newtype. Hence, the actual function is defined as:

fmap f (Callback g) = Callback $ \h -> g (h . f)

Hope that explains why a is covariant in (a -> IO ()) -> IO (). Hence, it's possible to define a Functor instance of Callback.