11 ms·

What are covariance and contravariance?

235 points by beliu 9y ago

ducttapecrown 9y ago
Why are covariance and contravariance important, and how do their type theory definitions differ from mathematical or statistical definitions of covariance and contravariance? 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?
- solipsism 9y ago
  The reason anyone cares is because we want static and yet flexible typing. The better a type system understands covariance and contravariance, the better it can be at statically checking complex relationships.
- ufo 9y ago
  You are getting the right idea there. It all has to do with how the typing rules look like in programming languages with subtyping. In a type system with subtyping, having a type A be a subtype of a type B (A <: B) means that we can pass a value of type A to any place where a value of type B would be expected. For basic types, the subtyping rules are pretty simple: just follow the class definition hierarchy. a Dog is an Animal, an Animal is an Object, and so on. For parameterized types, like collections (List[X]) or functions (Function[A,B]), it is a bit more complicated. The only way to go is to define the subtyping rule for T[X] in terms of the subtyping rule for X but which rule do we use? - T[A] <: T[B] iff A <: B ? (covariance) - T[A] <: T[B] iff A :> B ? (contravariance) - T[A] <: T[B] iff A = B ? (invariance) Well, it depends on the type! For example, function types (A->B) are contravariant with respect to the input type (the As) and covariant with respect to the output types (the Bs). For collections it depends on what operations are allowed. Read-only collections are covariant, write-only collections are contravariant and read-write collections are invariant. This last part is where knowing about variance becomes important for programmers. When it comes to user-defined parameterized types, the variance rules are different so to find out if a given type is covariant, contravariant or invariant the only option is to read the type annotations and documentation. And you also need to know what variance is to understand those annotations when you come across them.
bmc7505 9y ago
This a topic that also comes up in linear algebra. Is there any analogy between vectors and types, or is the terminology just coincidental? https://en.wikipedia.org/wiki/Covariance_and_contravariance_of_vectors https://en.wikipedia.org/wiki/Covariance_and_contravariance_...
- catnaroek 9y ago
  It's not a coincidence. The terms “covariance” and “contravariance” ultimately come from category theory.
  - jacobolus 9y ago
    According to Wikipedia: > The terms "covariant" and "contravariant" were introduced by James Joseph Sylvester in 1853 in the context of algebraic invariant theory, where, for instance, a system of simultaneous equations is contravariant in the variables. https://www.jstor.org/stable/108572 https://www.jstor.org/stable/108572
  - kmill 9y ago
    Next you're going to say "natural," "functor," and "category" come from category theory, too! :-)
noobermin 9y ago
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]). There we physicists go, confusing things again. [0] https://en.wikipedia.org/wiki/Functor#Covariance_and_contravariance https://en.wikipedia.org/wiki/Functor#Covariance_and_contrav...
- jacobolus 9y ago
  As they say, a comathematician is a device for turning cotheorems into ffee. If you’re interested in vectors/tensors, the relevant Wikipedia page is https://en.wikipedia.org/wiki/Covariance_and_contravariance_of_vectors https://en.wikipedia.org/wiki/Covariance_and_contravariance_...
- filmor 9y ago
  In this case it's the Category Theorists confusing things. Co- and contravariance of vectors with respect to their scale was introduced in the 1850s by Sylvester, Category Theory was formulated roughly 90 years later.
quantdev 9y ago
This was very interesting. 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. 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.
- jordigh 9y ago
  Can you figure out what the functor is? As another mathematician, if they're saying "contravariant" I expect to see something like a Galois functor. This kind of looks like a pullback or an evaluation functor, but I can't even see the categories it might be between. Is it the Hom functor?
  - rntz 9y ago
    See my other comment about co/contravariance as monotonocity/antimonotonicity. Since monotonicity is just functoriality when your categories are posetal, covariance is a special case of functoriality. More generally, you can see f(x) = Int -> x g(x) = x -> Int as, respectively, co- and contra-variant endofunctors on the category whose objects are types and whose arrows are definable functions in your programming language. And they're both just special-cases of the internal hom functor, hom : C^op * C -> C hom(x,y) = x -> y
    - jclulow 9y ago
      You keep using the word "just" in what feels like an unusual setting.
      - rntz 9y ago
        I use "just" to mean "exactly"; I say "X is just Y" to mean "X is exactly Y; when you have Y, you have X and vice-versa". I guess it might be kind of off-putting, because "just" implies the connection is boring or obvious, which is not what I mean to say.
OJFord 9y ago
This post presents a nice example, but only for the particular type system envisaged by the author. 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. 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.
- curryhoward 9y ago
  > 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. Covariance in the return type and contravariance in the argument type is the most general subtyping policy you can have for function types in a sound type system—it's not arbitrary. If instead you had covariance in the argument type, as some languages do, your type system is broken (as demonstrated in examples 1 and 2 in the article). If you had contravariance in the return type, this also breaks your type system (example 3). For some language designers, having a broken type system is acceptable. But it should not be presented as a legitimate option in an article about programming language theory. It's also sound to have invariance in argument and return types. But this is an arbitrary restriction with no clear benefits, except possibly eliminating the need to explain co/contravariance to users. I do try to avoid being prescriptive in the article, however; that's why the question is phrased as "Which of the following types could be subtypes of Dog -> Dog?" rather than "Which of the following types are subtypes of Dog -> Dog?". So we can have contravariance or invariance in the argument type, and covariance or invariance in the return type. But contravariance in the argument type and covariance in the return type is a strictly more general rule. And bivariance in either is certainly incorrect.
tritium 9y ago
This is typical technical jargon conflation in furtherance of interview pedantry. Please spare me. Looking at the words superficially, their definitions are easily discerned: Covariance: changing together, with similarity. Contravariance: changing in opposition to one another. 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." Try defining the word functional incorrectly during a technical interview and see what happens.
- coherentpony 9y ago
  > This is typical technical jargon conflation in furtherance of interview pedantry. That's an interesting point of view. I thought it was just an article explaining what covariance and contravariance are in the context of a type system. The author also went so far as to give some illustrative examples. The author could have just copied the definition from the dictionary. It seems like that would have been sufficient for you but it's unlikely that it would have been helpful for the majority of people that work in type systems and aren't aware of the more general concepts they work with. The author never mentioned anything about interview techniques.
- sethrin 9y ago
  Isn't the point of technical interviews to determine one's knowledge of useless trivia? That is to say, that is what is typically measured, and it's seemingly the rare workplace that even attempts to measure whether their hiring processes correlate with work performance. Hiring for developer positions is a cargo cult practice -- which is not necessarily a blanket condemnation, but as a non-traditional candidate it's certainly done me no favors. Generally, this is a hard problem with no simple solution: evaluating programmers requires almost as much domain knowledge as programming does. I'm pretty sure that you're not entirely wrong about what you say re: nerd signaling. However, while I share your frustration about the current state of the programming interview, I personally don't see much point in trying to buck the trend. If you really can't see your way to learning the trivia, then probably it's best to focus on your other strengths and show them what you do know. If they really only value the appearance of wisdom then you probably don't want to be working there anyway.
the_mitsuhiko 9y ago
Microsoft probably has the most logical docs on that: https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/covariance-contravariance/ https://docs.microsoft.com/en-us/dotnet/csharp/programming-g...
rntz 9y ago
Covariance and contravariance are just monotonicity and anti-monotonicity, applied to types ordered by subtyping. That is: if we have a function on types, say, the function `f` defined by: f(x) = Int -> x Then we say `f` is covariant because it is monotone: it preserves the subtype ordering on its argument. That is: if x <: y, then f(x) <: f(y) Similarly, if we consider `f` defined by: f(x) = x -> Int then this `f` is contravariant because it is anti-monotone: it reverses the subtype ordering on its argument. That is: if x <: y, then f(y) <: f(x) 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: dog -> dog 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.
- dheera 9y ago
  What about covfefe?
- techno_modus 9y ago
  > People tend to find covariance more intuitive than contravariance; unless the issue is pointed out, they tend to assume everything is covariant. I can easily understand where covariance is useful and meaningful while contravariance is somehow counterintuitive for me. Therefore I doubt if it is really needed (except for being a nice formal counterpart of covariance). In other words, would it be more natural to simply use covariance as a default rule while contravariance either being not available at all or used as a kind of exception (where you need to know what you are doing and understand the consequences)?
  - alipang 9y ago
    If you ever want function types you will always need both co- and contravariance as pointed out in OP's articles. Using covariance as a default is also not sound. Many things are "invariant", meaning neither co- or contravariant. This is already a sensible default. (It is however possible to automatically derive either property in some cases)
  - 9y ago
enriquto 9y ago
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) I feel that the examples in math are easier to understand that in programming. For example: - The integral of a function is invariant to additive changes of variable : \int f(a+x)dx = \int f(x)dx - The mean of a distribution is contravariant to additive changes of variable : \int f(a+x)xdx = -a + \int f(x)xdx - The mean of a distribution is covariant to shifts of the domain (same formula, because f(x-a) is a shift of size "a") - The variance of a distribution is invariant to additive changes of variable etc.
- emilypi 9y ago
  >In mathematics we call each of them "invariance" In math, we call it "variance" - as in invariance, contravariance, and covariance. They each refer to the character of a given functor between categories. A functor is covariant if a -> b maps to Fa -> Fb, contravariant if a -> b maps to Fb -> Fa, and invariant (otherwise known as exponential) if (a -> b) and (b -> a) map to Fa -> Fb. Every example of variant functors follow these laws. It helps to say that every higher-kinded type which admits a type parameter (i.e. List, Array, Option, etc) can be seen as an instance of a Functor (in fact, in haskell, they are instances of the Functor Typeclass). Variance is a statement about the functionality of containers given a pre-existing relationship between types they contain. In Math, keeping with the example set, the functor \pi_n : hTop* -> Grp is canonically covariant, while P: Set -> Set: s -> P(s), the powerset functor, is canonically contravariant. In keeping with the Scala tradition, Option and List, which you can check obey the functor laws. For more info, see Scalaz or Cats.
joshlemer 9y ago
Also see this handy infographic https://i.stack.imgur.com/W879X.png https://i.stack.imgur.com/W879X.png
- ridgeguy 9y ago
  Thanks for this, it helped me understand the matter being discussed.
tunesmith 9y ago
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 worse than my original worker's, but I sure don't mind if it's better. 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. 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. 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 Brazilian cherry". These guys aren't helpful when they show up in your parameter list.
- tome 9y ago
  This is a really great analogy which makes the issue obvious.
rectang 9y ago
The difference between covariance and contravariance is enough to get UW professor Dan Grossman jumping up and down: https://www.youtube.com/watch?v=pb_k8h6RuAY https://www.youtube.com/watch?v=pb_k8h6RuAY
asavinov 9y ago
Covariance can be thought of as a mechanism for overriding functions. Assume there is a (base) function f: X -> Y We want to override it by providing a new mapping from U to V: f: U -> V This mechanism is said to be covariant if the new function guarantees that If u <: x then v=f(u) <: y=f(x) This means that for each more specific input u in U the function returns more specific (not more general) output v in V.
Patient0 9y ago
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)
caseymarquis 9y ago
Something you learn to work around when you start getting creative with generics.
deleted 9y ago
[deleted]
pathikrit 9y ago
My quick and dirty tl;dr: https://gist.github.com/pathikrit/a7845f72645159646fdb632bc334771a https://gist.github.com/pathikrit/a7845f72645159646fdb632bc3... Let C<A> be a higher-kinded type e.g. in List<Animal>, List is C and Animal is A. Let S be a subtype of T e.g. in class Cat extends Animal, Cat is S and Animal is T 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> 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> If neither C<T> and nor C<S> are subtypes of the other, thenC is invariant on T
elvongray 9y ago
Was thinking of Tensor Analysis when I saw the title

235 points by beliu 9y ago

Why are covariance and contravariance important, and how do their type theory definitions differ from mathematical or statistical definitions of covariance and contravariance? 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?

solipsism 9y ago
The reason anyone cares is because we want static and yet flexible typing. The better a type system understands covariance and contravariance, the better it can be at statically checking complex relationships.
ufo 9y ago
You are getting the right idea there. It all has to do with how the typing rules look like in programming languages with subtyping. In a type system with subtyping, having a type A be a subtype of a type B (A <: B) means that we can pass a value of type A to any place where a value of type B would be expected. For basic types, the subtyping rules are pretty simple: just follow the class definition hierarchy. a Dog is an Animal, an Animal is an Object, and so on. For parameterized types, like collections (List[X]) or functions (Function[A,B]), it is a bit more complicated. The only way to go is to define the subtyping rule for T[X] in terms of the subtyping rule for X but which rule do we use? - T[A] <: T[B] iff A <: B ? (covariance) - T[A] <: T[B] iff A :> B ? (contravariance) - T[A] <: T[B] iff A = B ? (invariance) Well, it depends on the type! For example, function types (A->B) are contravariant with respect to the input type (the As) and covariant with respect to the output types (the Bs). For collections it depends on what operations are allowed. Read-only collections are covariant, write-only collections are contravariant and read-write collections are invariant. This last part is where knowing about variance becomes important for programmers. When it comes to user-defined parameterized types, the variance rules are different so to find out if a given type is covariant, contravariant or invariant the only option is to read the type annotations and documentation. And you also need to know what variance is to understand those annotations when you come across them.

bmc7505 9y ago

This a topic that also comes up in linear algebra. Is there any analogy between vectors and types, or is the terminology just coincidental? https://en.wikipedia.org/wiki/Covariance_and_contravariance_of_vectors https://en.wikipedia.org/wiki/Covariance_and_contravariance_...

catnaroek 9y ago
It's not a coincidence. The terms “covariance” and “contravariance” ultimately come from category theory.
- jacobolus 9y ago
  According to Wikipedia: > The terms "covariant" and "contravariant" were introduced by James Joseph Sylvester in 1853 in the context of algebraic invariant theory, where, for instance, a system of simultaneous equations is contravariant in the variables. https://www.jstor.org/stable/108572 https://www.jstor.org/stable/108572
- kmill 9y ago
  Next you're going to say "natural," "functor," and "category" come from category theory, too! :-)

noobermin 9y ago

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]). There we physicists go, confusing things again. [0] https://en.wikipedia.org/wiki/Functor#Covariance_and_contravariance https://en.wikipedia.org/wiki/Functor#Covariance_and_contrav...

jacobolus 9y ago
As they say, a comathematician is a device for turning cotheorems into ffee. If you’re interested in vectors/tensors, the relevant Wikipedia page is https://en.wikipedia.org/wiki/Covariance_and_contravariance_of_vectors https://en.wikipedia.org/wiki/Covariance_and_contravariance_...
filmor 9y ago
In this case it's the Category Theorists confusing things. Co- and contravariance of vectors with respect to their scale was introduced in the 1850s by Sylvester, Category Theory was formulated roughly 90 years later.

quantdev 9y ago

This was very interesting. 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. 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.

jordigh 9y ago
Can you figure out what the functor is? As another mathematician, if they're saying "contravariant" I expect to see something like a Galois functor. This kind of looks like a pullback or an evaluation functor, but I can't even see the categories it might be between. Is it the Hom functor?
- rntz 9y ago
  See my other comment about co/contravariance as monotonocity/antimonotonicity. Since monotonicity is just functoriality when your categories are posetal, covariance is a special case of functoriality. More generally, you can see f(x) = Int -> x g(x) = x -> Int as, respectively, co- and contra-variant endofunctors on the category whose objects are types and whose arrows are definable functions in your programming language. And they're both just special-cases of the internal hom functor, hom : C^op * C -> C hom(x,y) = x -> y
  - jclulow 9y ago
    You keep using the word "just" in what feels like an unusual setting.
    - rntz 9y ago
      I use "just" to mean "exactly"; I say "X is just Y" to mean "X is exactly Y; when you have Y, you have X and vice-versa". I guess it might be kind of off-putting, because "just" implies the connection is boring or obvious, which is not what I mean to say.

OJFord 9y ago

This post presents a nice example, but only for the particular type system envisaged by the author. 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. 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.

curryhoward 9y ago
> 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. Covariance in the return type and contravariance in the argument type is the most general subtyping policy you can have for function types in a sound type system—it's not arbitrary. If instead you had covariance in the argument type, as some languages do, your type system is broken (as demonstrated in examples 1 and 2 in the article). If you had contravariance in the return type, this also breaks your type system (example 3). For some language designers, having a broken type system is acceptable. But it should not be presented as a legitimate option in an article about programming language theory. It's also sound to have invariance in argument and return types. But this is an arbitrary restriction with no clear benefits, except possibly eliminating the need to explain co/contravariance to users. I do try to avoid being prescriptive in the article, however; that's why the question is phrased as "Which of the following types could be subtypes of Dog -> Dog?" rather than "Which of the following types are subtypes of Dog -> Dog?". So we can have contravariance or invariance in the argument type, and covariance or invariance in the return type. But contravariance in the argument type and covariance in the return type is a strictly more general rule. And bivariance in either is certainly incorrect.

tritium 9y ago

This is typical technical jargon conflation in furtherance of interview pedantry. Please spare me. Looking at the words superficially, their definitions are easily discerned: Covariance: changing together, with similarity. Contravariance: changing in opposition to one another. 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." Try defining the word functional incorrectly during a technical interview and see what happens.

coherentpony 9y ago
> This is typical technical jargon conflation in furtherance of interview pedantry. That's an interesting point of view. I thought it was just an article explaining what covariance and contravariance are in the context of a type system. The author also went so far as to give some illustrative examples. The author could have just copied the definition from the dictionary. It seems like that would have been sufficient for you but it's unlikely that it would have been helpful for the majority of people that work in type systems and aren't aware of the more general concepts they work with. The author never mentioned anything about interview techniques.
sethrin 9y ago
Isn't the point of technical interviews to determine one's knowledge of useless trivia? That is to say, that is what is typically measured, and it's seemingly the rare workplace that even attempts to measure whether their hiring processes correlate with work performance. Hiring for developer positions is a cargo cult practice -- which is not necessarily a blanket condemnation, but as a non-traditional candidate it's certainly done me no favors. Generally, this is a hard problem with no simple solution: evaluating programmers requires almost as much domain knowledge as programming does. I'm pretty sure that you're not entirely wrong about what you say re: nerd signaling. However, while I share your frustration about the current state of the programming interview, I personally don't see much point in trying to buck the trend. If you really can't see your way to learning the trivia, then probably it's best to focus on your other strengths and show them what you do know. If they really only value the appearance of wisdom then you probably don't want to be working there anyway.

the_mitsuhiko 9y ago

Microsoft probably has the most logical docs on that: https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/covariance-contravariance/ https://docs.microsoft.com/en-us/dotnet/csharp/programming-g...

rntz 9y ago

Covariance and contravariance are just monotonicity and anti-monotonicity, applied to types ordered by subtyping. That is: if we have a function on types, say, the function `f` defined by: f(x) = Int -> x Then we say `f` is covariant because it is monotone: it preserves the subtype ordering on its argument. That is: if x <: y, then f(x) <: f(y) Similarly, if we consider `f` defined by: f(x) = x -> Int then this `f` is contravariant because it is anti-monotone: it reverses the subtype ordering on its argument. That is: if x <: y, then f(y) <: f(x) 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: dog -> dog 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.

dheera 9y ago
What about covfefe?
techno_modus 9y ago
> People tend to find covariance more intuitive than contravariance; unless the issue is pointed out, they tend to assume everything is covariant. I can easily understand where covariance is useful and meaningful while contravariance is somehow counterintuitive for me. Therefore I doubt if it is really needed (except for being a nice formal counterpart of covariance). In other words, would it be more natural to simply use covariance as a default rule while contravariance either being not available at all or used as a kind of exception (where you need to know what you are doing and understand the consequences)?
- alipang 9y ago
  If you ever want function types you will always need both co- and contravariance as pointed out in OP's articles. Using covariance as a default is also not sound. Many things are "invariant", meaning neither co- or contravariant. This is already a sensible default. (It is however possible to automatically derive either property in some cases)
- 9y ago

enriquto 9y ago

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) I feel that the examples in math are easier to understand that in programming. For example: - The integral of a function is invariant to additive changes of variable : \int f(a+x)dx = \int f(x)dx - The mean of a distribution is contravariant to additive changes of variable : \int f(a+x)xdx = -a + \int f(x)xdx - The mean of a distribution is covariant to shifts of the domain (same formula, because f(x-a) is a shift of size "a") - The variance of a distribution is invariant to additive changes of variable etc.

emilypi 9y ago
>In mathematics we call each of them "invariance" In math, we call it "variance" - as in invariance, contravariance, and covariance. They each refer to the character of a given functor between categories. A functor is covariant if a -> b maps to Fa -> Fb, contravariant if a -> b maps to Fb -> Fa, and invariant (otherwise known as exponential) if (a -> b) and (b -> a) map to Fa -> Fb. Every example of variant functors follow these laws. It helps to say that every higher-kinded type which admits a type parameter (i.e. List, Array, Option, etc) can be seen as an instance of a Functor (in fact, in haskell, they are instances of the Functor Typeclass). Variance is a statement about the functionality of containers given a pre-existing relationship between types they contain. In Math, keeping with the example set, the functor \pi_n : hTop* -> Grp is canonically covariant, while P: Set -> Set: s -> P(s), the powerset functor, is canonically contravariant. In keeping with the Scala tradition, Option and List, which you can check obey the functor laws. For more info, see Scalaz or Cats.

joshlemer 9y ago

Also see this handy infographic https://i.stack.imgur.com/W879X.png https://i.stack.imgur.com/W879X.png

ridgeguy 9y ago
Thanks for this, it helped me understand the matter being discussed.

tunesmith 9y ago

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 worse than my original worker's, but I sure don't mind if it's better. 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. 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. 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 Brazilian cherry". These guys aren't helpful when they show up in your parameter list.

tome 9y ago
This is a really great analogy which makes the issue obvious.

rectang 9y ago

The difference between covariance and contravariance is enough to get UW professor Dan Grossman jumping up and down: https://www.youtube.com/watch?v=pb_k8h6RuAY https://www.youtube.com/watch?v=pb_k8h6RuAY

asavinov 9y ago

Covariance can be thought of as a mechanism for overriding functions. Assume there is a (base) function f: X -> Y We want to override it by providing a new mapping from U to V: f: U -> V This mechanism is said to be covariant if the new function guarantees that If u <: x then v=f(u) <: y=f(x) This means that for each more specific input u in U the function returns more specific (not more general) output v in V.

Patient0 9y ago

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)

caseymarquis 9y ago

Something you learn to work around when you start getting creative with generics.

deleted 9y ago

[deleted]

pathikrit 9y ago

My quick and dirty tl;dr: https://gist.github.com/pathikrit/a7845f72645159646fdb632bc334771a https://gist.github.com/pathikrit/a7845f72645159646fdb632bc3... Let C<A> be a higher-kinded type e.g. in List<Animal>, List is C and Animal is A. Let S be a subtype of T e.g. in class Cat extends Animal, Cat is S and Animal is T 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> 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> If neither C<T> and nor C<S> are subtypes of the other, thenC is invariant on T

elvongray 9y ago

Was thinking of Tensor Analysis when I saw the title