4 ms·
I was super confused by contravariant functors until someone gave me a concrete example of an instance of it as "the left side of an arrow". With a regular fun
by vore 6y ago
I was super confused by contravariant functors until someone gave me a concrete example of an instance of it as "the left side of an arrow".
With a regular functor you have:
fmap :: Functor f => (a -> b) -> f a -> f b
and you can think of something relatively straightforward type that fulfills it it, e.g.:
newtype Identity a = Identity a
instance Functor Identity where
fmap f (Identity x) = Identity (f x)
With a contravariant functor you have:
contramap :: Contravariant f => (a -> b) -> f b -> f a
The Identity type can't fulfill Contravariant, because it makes no sense to apply some transformation a -> b to a value and somehow get the preimage of it. However:
newtype Op a b = Op (b -> a)
instance Contravariant (Op a) where
contramap f (Op g) = Op (g . f)
Unwrapping this all, you get something like:
contramap :: (a -> b) -> (b -> c) -> (a -> c)
which makes a lot more sense! You can apply some mapping from a -> b before going from b -> c, giving you a -> c: the contravariant mapping of a function is just the reverse composition of a function!
Of course, there are other kinds of contravariant functors, but this was the one that stuck out the most to me.
- vore 6y agoI missed a step: contramap :: (a -> b) -> Op c b -> Op c a -- substitute Contravariant f for the Op instance, c is introduced as a new type variable contramap :: (a -> b) -> (b -> c) -> (a -> c)
- bollu 6y agoA slightly more concrete version of this is data Predicate a = Predicate (a -> Bool) this naturally has a contravariant functor instance: if you can tell me whether something is true for "a", and you can convert "b -> a", then how do you tell me whether something is true for "b"? Convert the "b" to an "a" and see if it's true for "a". Formally, you get the instance contramap :: (b -> a) -> Predicate a -> Predicate b contramap :: (b -> a) -> (a -> Bool) -> (b -> Bool) The picture to have in mind is to imagine A as a space, and then to know that some things are true in A (color them green) while others are false (color them red). If you now want to color another space B using this space A, should you have A -> B, or B -> A? some thought reveals that A -> B may tell us inconsistent colourings. For example, say we have a map {red, green} -> { b } where both "red" and "green" map to "b". So what color do we assign "b"? There is no reasonable choice. On the other hand, say we have a function B -> A. Since each element in b maps to one element of A, we can say color(b) = color of element that b maps to. We need the fact that a function maps one value in the domain to exactly one value in the codomain for this to work. I tend to imagine the function from B to A as threads, whose endpoints in A are soaked with dye. This dye "moves backwards" towards B. The uniqueness in colors assigned to B is given by the fact that we can only have one thread from each point in B.