Suppose that T is a functor. Then we have
fmap :: (a -> b) -> T a -> T b
Now try to implement it.
instance Functor T where fmap f (T g) = T $ \x -> _y
It’s clear that we start with something like this and combine the values f , g and x somehow to calculate the value for y correct type. How can we do this? Well, notice that I called him _y , which says GHC. I need help figuring out what to put there. What does the GHC say?
<interactive>:7:28: error: • Found hole: _y :: Int Or perhaps '_y' is mis-spelled, or not in scope • In the expression: _y In the second argument of '($)', namely '\ x -> _y' In the expression: T $ \ x -> _y • Relevant bindings include x :: b (bound at <interactive>:7:23) g :: a -> Int (bound at <interactive>:7:13) f :: a -> b (bound at <interactive>:7:8) fmap :: (a -> b) -> T a -> T b (bound at <interactive>:7:3)
So now we are clearly talking about the types of everything relevant, right? We need to somehow return Int , and we need to build it:
x :: b g :: a -> Int f :: a -> b
Well, okay, the only thing that we can create Int is g , so let's fill it in, leaving the g argument blank to ask GHC for more help:
instance Functor T where fmap f (T g) = T $ \x -> g _y <interactive>:7:31: error: • Found hole: _y :: a Where: 'a' is a rigid type variable bound by the type signature for: fmap :: forall a b. (a -> b) -> T a -> T b at <interactive>:7:3 Or perhaps '_y' is mis-spelled, or not in scope • In the first argument of 'g', namely '(_y)' In the expression: g (_y) In the second argument of '($)', namely '\ x -> g (_y)' • Relevant bindings include x :: b (bound at <interactive>:7:23) g :: a -> Int (bound at <interactive>:7:13) f :: a -> b (bound at <interactive>:7:8) fmap :: (a -> b) -> T a -> T b (bound at <interactive>:7:3)
Well, we could predict this ourselves: to call g , we need a value of type a from somewhere. But we do not have any values of type a in scope, and we have no functions that return a value of type a ! We are stuck: it is impossible to get the value of the type that we want now, although at every step we did the only possible thing: we could not make a backup and try differently.
Why did this happen? Because if I give you a function like a -> Int and say "but, by the way, here is a function from a -> b , please return the function from b -> Int instead," you cannot actually use the function from a -> b , because no one ever gives you a to call him! If I gave you a function from b -> a , that would be very useful, right? You can create a function from b -> Int , and then first call the function b -> a to get a , and then call the original function a -> Int to get the desired Int .
And about what a contravariant functor is: we cancel the arrow in the function passed to fmap , so it can fmap over the things you need (function arguments) instead of what you “have” (specific values, return values of functions, and t .d.).
In addition: I previously claimed that we did the “only possible thing” at each stage, which was a bit of a fix. We cannot build Int from f , g and x , but, of course, we can release all kinds of numbers from the ether. We don’t know anything about type b , so we cannot get the Int that was obtained from it in any way, but we could just say “always return zero”, and this technically satisfies the type check
instance Functor T where fmap f (T g) = T $ const 0
Obviously, this looks completely wrong, since it seems that f and g should be very important, and we ignore them! But he checks the type, so we're fine, right?
No, this violates one of Functor's laws:
fmap id = id
We can prove it quite easily:
fmap id (T $ const 5) = (T $ const 0) /= (T $ const 5)
And now we really tried everything: the only way to build Int without using our type b at all is to exclude it from nothing, and all such applications will be isomorphic to using const , which violates the laws of Functor.