Covariance and contravariance are just monotonicity and anti-monotonicity, applied to types ordered by subtyping.<p>That is: if we have a function <i>on types</i>, say, the function `f` defined by:<p><pre><code> f(x) = Int -> x
</code></pre>
Then we say `f` is covariant because it is monotone: it preserves the subtype ordering on its argument. That is:<p><pre><code> if x <: y, then f(x) <: f(y)
</code></pre>
Similarly, if we consider `f` defined by:<p><pre><code> f(x) = x -> Int
</code></pre>
then this `f` is contravariant because it is anti-monotone: it reverses the subtype ordering on its argument. That is:<p><pre><code> if x <: y, then f(y) <: f(x)
</code></pre>
People tend to find covariance more intuitive than contravariance; unless the issue is pointed out, they tend to assume everything is covariant. They see a type, say:<p><pre><code> dog -> dog
</code></pre>
and they assume "oh, every dog is an animal, so I can put 'animal' in place of 'dog' and it'll be more general (i.e. a supertype)". This is false, as the article points out.
Also see this handy infographic <a href="https://i.stack.imgur.com/W879X.png" rel="nofollow">https://i.stack.imgur.com/W879X.png</a>
One of the ways I like to look at it is that I'm a foreman and one of my construction workers can't show up, and I need a substitute, I don't want someone that is even less useful than my worker. A really good substitute is someone that can do everything that my original worker could do, and maybe then some even if I don't take advantage of it. Meanwhile, I don't want his results to be <i>worse</i> than my original worker's, but I sure don't mind if it's better.<p>In other words, if my original worker only knows how to turn a Dog into a Dog, and that was good enough, the most useful substitute is someone who can take any Animal and turn it into any special kind of dog.<p>Or maybe I care about 2x4's, and my normal guy only knows how to turn Cherry into 2x4's and isn't trained on anything else, even though that suited my needs. The best sub is someone who can take lots of kinds of wood and turn it into different kinds of posts and planks; I'm just only taking advantage of his 2x4 skills.<p>Unfortunately a lot of programmers design subclasses by saying "hey look, I'm good at starting with a schnauzer" or "hey look, I'm good at starting with <i>Brazilian</i> cherry". These guys aren't helpful when they show up in your parameter list.
This was very interesting.<p>As a mathematician with no comp-sci type knowledge, my only understanding of inheritance is the "is a" rule. Using this, I realized that a subtype of the set of functions from Dog to Dog must be a set of functions such that each function could be treated as a function from Dog to Dog under an appropriate restriction. This would be the only way for such a set to satisfy what felt like the "is a" inheritance rule.<p>In other words, a set of functions from A to B where Dog is contained in A and B is contained in Dog would be a subtype of the set of functions from Dog to Dog. So Animals -> Greyhound works.
So I used to think covariance and contravariance were related to covectors and vectors from physics, but in fact, our terminology is in fact confusing the concept (almost "opposite" actually) that is now accepted in math. (See comment on wiki[0]).<p>There we physicists go, confusing things again.<p>[0] <a href="https://en.wikipedia.org/wiki/Functor#Covariance_and_contravariance" rel="nofollow">https://en.wikipedia.org/wiki/Functor#Covariance_and_contrav...</a>
Why are covariance and contravariance important, and how do their type theory definitions differ from mathematical or statistical definitions of covariance and contravariance?<p>Is it just a distinction of which direction the type hierarchy flows, and the consequences that must have with regard to functions in order for logical consistency to be maintained?
Microsoft probably has the most logical docs on that: <a href="https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/covariance-contravariance/" rel="nofollow">https://docs.microsoft.com/en-us/dotnet/csharp/programming-g...</a>
My quick and dirty tl;dr:
<a href="https://gist.github.com/pathikrit/a7845f72645159646fdb632bc334771a" rel="nofollow">https://gist.github.com/pathikrit/a7845f72645159646fdb632bc3...</a><p>Let C<A> be a higher-kinded type e.g. in List<Animal>, List is C and Animal is A.<p>Let S be a subtype of T e.g. in class Cat extends Animal, Cat is S and Animal is T<p>If C<S> is a subtype of C<T>, then C is covaraint on T e.g. List<Cat> is a subtype of List<Animal><p>If C<T> is a subtype of C<S>, then C is contravariant on T e.g. Predicate<Animal> is a subtype of Predicate<Cat><p>If neither C<T> and nor C<S> are subtypes of the other, thenC is invariant on T
Covariance can be thought of as a mechanism for overriding functions. Assume there is a (base) function<p><pre><code> f: X -> Y
</code></pre>
We want to override it by providing a new mapping from U to V:<p><pre><code> f: U -> V
</code></pre>
This mechanism is said to be covariant if the new function guarantees that<p><pre><code> If u <: x then v=f(u) <: y=f(x)
</code></pre>
This means that for each more specific input u in U the function returns more specific (not more general) output v in V.
This post presents a nice example, but only for the particular type system envisaged by the author.<p>At least, I believe that the point of conceiving of 'covariance' and 'contravariance' is that we may have or not have either, in input or return types.<p>The submission presents one incarnation, a common one I believe, but nevertheless I think if the goal's to understand variance, the concept must be distinguished from implementation.
This a topic that also comes up in linear algebra. Is there any analogy between vectors and types, or is the terminology just coincidental? <a href="https://en.wikipedia.org/wiki/Covariance_and_contravariance_of_vectors" rel="nofollow">https://en.wikipedia.org/wiki/Covariance_and_contravariance_...</a>
Great article - I'm impressed that it covers every discovery I've painstakingly worked through over the years, all succinctly expressed on one page: Java arrays, immutable lists and even the fact that Eiffel got it wrong (which I remember puzzling over with a colleague back in the 90s)
The difference between covariance and contravariance is enough to get UW professor Dan Grossman jumping up and down: <a href="https://www.youtube.com/watch?v=pb_k8h6RuAY" rel="nofollow">https://www.youtube.com/watch?v=pb_k8h6RuAY</a>
In mathematics we call each of them "invariance", if we do not want to sound too pedantic (or unless the distinction cannot be deduced easily from context)<p>I feel that the examples in math are easier to understand that in programming. For example:<p>- The integral of a function is invariant to additive changes of variable : \int f(a+x)dx = \int f(x)dx<p>- The mean of a distribution is contravariant to additive changes of variable : \int f(a+x)xdx = -a + \int f(x)xdx<p>- The mean of a distribution is covariant to shifts of the domain (same formula, because f(x-a) is a shift of size "a")<p>- The variance of a distribution is invariant to additive changes of variable<p>etc.
This is typical technical jargon conflation in furtherance of interview pedantry. Please spare me.<p>Looking at the words superficially, their definitions are easily discerned:<p><pre><code> Covariance: changing together, with similarity.
Contravariance: changing in opposition to one another.
</code></pre>
But, as part of strategic nerd signaling in interviews to parse what a candidate has been reading lately, you'll encounter middle managers that will cull contending close-call applicants based on trivia like this. Similar technical jargon that isn't what you think it might be, due to some seminal blog post include "composition" or "isomorphic" or perhaps most obviously, the simple-but-loaded term "functional."<p>Try defining the word functional incorrectly during a technical interview and see what happens.