12

The C# spec states that an argument type cannot be both covariant and contravariant at the same time.

This is apparent when creating a covariant or contravariant interface you decorate your type parameters with "out" or "in" respectively. There is not option that allows both at the same time ("outin").

Is this limitation simply a language specific constraint or are there deeper, more fundamental reasons based in category theory that would make you not want your type to be both covariant and contravariant?

Edit:

My understanding was that arrays were actually both covariant and contravariant.

public class Pet{}
public class Cat : Pet{}
public class Siamese : Cat{}
Cat[] cats = new Cat[10];
Pet[] pets = new Pet[10];
Siamese[] siameseCats = new Siamese[10];

//Cat array is covariant
pets = cats; 
//Cat array is also contravariant since it accepts conversions from wider types
cats = siameseCats; 
William Edmondson
  • 3,619
  • 3
  • 32
  • 41
  • 1
    I am confused by your last statement; how is it that this is a demonstration of contravariance? "Siamese" is a *narrower* type than "Cat", just as "Cat" is a narrower type than "Pet". – Eric Lippert Dec 25 '10 at 01:46
  • All cats are pets and all Siamese cats are cats, so that only demonstrates covariance. – Gabe Dec 25 '10 at 02:55
  • Eric - you are right that doesn't make any sense. – William Edmondson Dec 25 '10 at 03:50
  • There are situations where it would be useful for arrays to be contravariant in the same sense that they are covariant, but for writes rather than reads, i.e. if a routine expects an array into which it can store Derived, it would be possible for it to work given an array of Base. The best approach to achieve that might perhaps have been for arrays to implement IReadableByIndex, which would be covariant, and IWritableByIndex, which would be contravariant, so routines that only need to read or write an array could make the proper choice. – supercat Jul 15 '11 at 22:00
  • Incidentally, one may write a routine to sort any array-ish object, without having to know its type, if the array-ish object supports a non-generic ISortableByIndex interface with methods CompareAt(int index1, int index2) and SwapAt(int index1, int index2). – supercat Jul 15 '11 at 22:08

7 Answers7

25

As others have said, it is logically inconsistent for a generic type to be both covariant and contravariant. There are some excellent answers here so far, but let me add two more.

First off, read my article on the subject of variance "validity":

http://blogs.msdn.com/b/ericlippert/archive/2009/12/03/exact-rules-for-variance-validity.aspx

By definition, if a type is "covariantly valid" then it is not usable in a contravariant way. If it is "contravariantly valid" then it is not usable in a covariant way. Something that is both covariantly valid and contravariantly valid is not usable in either a covariant or contravariant way. That is, it is invariant. So, there is the union of covariant and contravariant: their union is invariant.

Second, let's suppose for a moment that you got your wish and that there was a type annotation that worked the way I think you want:

interface IBurger<in and out T> {}

Suppose you have an IBurger<string>. Because it is covariant, that is convertible to IBurger<object>. Because it is contravariant, that is in turn convertible to IBurger<Exception>, even though "string" and "Exception" have nothing whatsoever in common. Basically "in and out" means that IBurger<T1> is convertible to any type IBurger<T2> for any two reference types T1 and T2. How is that useful? What would you do with such a feature? Suppose you have an IBurger<Exception>, but the object is actually an IBurger<string>. What could you do with that, that both takes advantage of the fact that the type argument is Exception, and allows that type argument to be a complete lie, because the "real" type argument is an utterly unrelated type?

To answer your follow-up question: implicit reference type conversions involving arrays are covariant; they are not contravariant. Can you explain why you incorrectly believe them to be contravariant?

Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
  • The IBurger example is exactly what I was looking for. – William Edmondson Dec 25 '10 at 03:53
  • As far as "Can you explain why you incorrectly believe them to be contravariant" after you pointed it out it is obviously not contravariant. – William Edmondson Dec 25 '10 at 03:57
  • Eric: I still think invariance is the intersection, not union, of covariance and contravariance. But maybe I'm thinking of the set of types that can be used in a covariant or contravariant context, rather than set of generic types which act covariantly or contravariantly. – Ben Voigt Dec 25 '10 at 04:36
  • I would agree that a type which is both covariantly valid and invariantly valid wouldn't be invariant--it would be unusable as a type within the interface. I can think of cases where covariance or contravariance might be useful in a marker interface, but since interfaces can derive from multiple interfaces, I can't think of a case where arbitrary variance would be useful. If a generic interface might be passed to a routine that wouldn't care about the generic type, it should derive from a non-generic version, and the routine should use that as its argument type. – supercat Mar 24 '11 at 14:55
  • 5
    @Eric Lippert: I found this answer after answering this [question](http://stackoverflow.com/q/6709148/45914). The only thing I want to say is I get and appreciate your In-N-Out Burger joke. – jason Jul 15 '11 at 15:35
  • 2
    @Jason: Glad you liked it, though I'll tell you, its a good thing that the primary function of my sense of humour is to amuse *me*. – Eric Lippert Jul 15 '11 at 15:53
  • 1
    @Eric Lippert: I know what you mean. My partner is constantly saying to me "I'm glad *you* find it funny" after I deliver a joke to her. – jason Jul 15 '11 at 15:56
8

Covariance and contravariance are mutually exclusive. Your question is like asking if set A can be both a superset of set B and a subset of set B. In order for set A to be both a subset and superset of set B, set A must be equal to set B, so then you would just ask if set A is equal to set B.

In other words, asking for covariance and contravariance on the same argument is like asking for no variance at all (invariance), which is the default. Thus, there's no need for a keyword to specify it.

Gabe
  • 84,912
  • 12
  • 139
  • 238
  • Umm, that is possible, it requires that A is identically equal to B. In other words, invariance. – Ben Voigt Dec 24 '10 at 20:37
  • Ben: Thanks, I've clarified it hopefully. – Gabe Dec 24 '10 at 20:43
  • I thought invariance was when neither covariance nor contravariance applied. – William Edmondson Dec 24 '10 at 21:17
  • Additionally, aren't arrays both covariant and contravariant? If so then the two aren't mutually exclusive because the feature actually exists in the wild. – William Edmondson Dec 24 '10 at 21:19
  • @William: Arrays are strictly covariant. Invariance is the intersection of covariance and contravariance. – Gabe Dec 25 '10 at 02:53
  • @Ben: Variance is a property of operations on types, not objects. A property of type `Cat` is that it can be assigned to a variable of type `Pet`. Since an object of type `Cat[]` can be assigned to a variable of type `Pet[]`, the `[]` (array) operation has the property of covariance. – Gabe Dec 25 '10 at 05:01
  • @Ben: Please define "covariant" and "subtype" as you use them, because your definitions are clearly different than those used by the rest of us. My definition of "covariant" has nothing to do with type safety or subtypes, and my definition of "subtype" is "derives from" (e.g. `IEnumerator` is not a subtype of `IEnumerator` because the former is not derived from the latter). – Gabe Dec 25 '10 at 07:07
  • But `X[] <: Y[]` under Liskov implies that `X` is identically `Y`, hence the array relation is invariant. – Ben Voigt Dec 26 '10 at 06:09
  • Ben: While it's perfectly valid to use "Liskov substitutable" for your definition of covariance, it is not of much use in the discussion of C#. The C# type checker knows nothing of Liskov, so its own substitution rules determine variance. Since the C# compiler will allow you to use a value of type `Cat[]` everywhere that a value of type `Pet[]` may be used, arrays in C# are covariant. Likewise, `IEnumerable` only became covariant in C# 4 because that's when the type annotation was added to the interface. – Gabe Dec 26 '10 at 06:59
  • Ben: I can't believe we're both reading the same language. At the beginning of your link Eric states "arrays where the element type is a reference type are covariant". It doesn't say anything about pretending or not really being. It *does* say that this particular kind of covariance is "broken" (because it isn't typesafe), but that's a far cry from being invariant. – Gabe Dec 31 '10 at 22:56
  • @Gabe: I think we're repeating the entire set of comments on that blog post. Speaking of which, are you the same Gabe that commented there? In any case, I think we're both agreed that the array relation is C#-covariant (which is not really typesafe) but Liskov-invariant. So I propose that, for the benefit of future readers, you reword your second comment (#5 in the sequence) to mention that C# allows array covariance, but (taking note that the question asked about the theory), arrays are actually Liskov-invariant so covariant usage is broken/untypesafe -- and then we nuke this intervening mess – Ben Voigt Jan 01 '11 at 04:45
  • BTW: The C# design engineers also [discuss covariance in C# in considerable depth](http://blogs.msdn.com/b/ericlippert/archive/tags/covariance+and+contravariance/), including [the broken covariance of arrays](http://blogs.msdn.com/b/ericlippert/archive/2007/10/17/covariance-and-contravariance-in-c-part-two-array-covariance.aspx). – Ben Voigt Jan 01 '11 at 04:48
5

Covariance is possible for types you never input (e.g. member functions can use it as a return type or out parameter, but never as an input parameter). Contravariance is possible for types you never output (e.g. as an input parameter, but never as a return type or out parameter).

If you made a type parameter both covariant and contravariant, you couldn't input it and you couldn't output it -- you couldn't use it at all.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
1

Without out and in keywords argument is Covariance and Contravariance isn't it?

in means that argument can only be used as function argument type

out means that argument can be used only as return value type

without in and out means that it can be used as argument type and as return value type

Arsen Mkrtchyan
  • 49,896
  • 32
  • 148
  • 184
  • Insofar as the intersection of covariance and contravariance is invariance, yes. I think the OP wants the union of covariance and contravariance, and that just isn't possible. – Ben Voigt Dec 24 '10 at 20:35
0

Is this limitation simply a language specific constraint or are there deeper, more fundamental reasons based in category theory that would make you not want your type to be both covariant and contravariant?

No, there is a much simpler reason based in basic logic (or just common sense, whichever you prefer): a statement cannot be both true and not true at the same time.

Covariance means S <: T ⇒ G<S> <: G<T> and contravariance means S <: T ⇒ G<T> <: G<S>. It should be pretty obvious that these can never be true at the same time.

Jörg W Mittag
  • 363,080
  • 75
  • 446
  • 653
  • 4
    It's not obvious to me. Why is it obvious that this can *never* be true? Isn't it the case that there could be relations defined on a set such that G <: G and G >: G ? They might not be useful or interesting relations, but I don't see why they are *impossible*. – Eric Lippert Dec 25 '10 at 01:44
  • 1
    @Eric Lippert: you are correct, of course. In this specific case I took `<:` to be the usual subtype relationship. A type cannot be both a supertype and a subtype of another type unless they are the *same* type. (At least, I don't see a way how that would work in C#'s type system.) Assuming that `S` and `T` are different types, I don't see it desirable to have `G` and `G` be the same type. – Jörg W Mittag Dec 25 '10 at 15:53
  • Well, the actual relationship in the type system is *assignment compatibility* rather than *subtyping*; there are subtle differences. In the CLR type system, int and uint are not subtypes of each other but they are assignment compatible with each other. Because arrays are covariant in the CLR type system, int[] and uint[] are *also* assignment compatible with each other, even though they are not subtypes either. In this specific case where G is "make an array type" it just so happens that G <: G *and* G :> G but G != G. – Eric Lippert Dec 25 '10 at 16:32
0

What you can do with "Covariant"?

Covariant uses the modifier out, meaning that the type can be an output of a method, but not an input parameter.

Suppose you have these class and interface:

interface ICanOutput<out T> { T getAnInstance(); }

class Outputter<T> : ICanOutput<T>
{
    public T getAnInstance() { return someTInstance; }
}

Now suppose you have the types TBig inheiriting TSmall. This means that a TBig instance is always a TSmall instance too; but a TSmall instance is not always a TBig instance. (The names were chosen to be easy to visualize TSmall fitting inside TBig)

When you do this (a classic covariant assignment):

//a real instance that outputs TBig
Outputter<TBig> bigOutputter = new Outputter<TBig>();

//just a view of bigOutputter
ICanOutput<TSmall> smallOutputter = bigOutputter;
  • bigOutputter.getAnInstance() will return a TBig
  • And because smallOutputter was assigned with bigOutputter:
    • internally, smallOutputter.getAnInstance() will return TBig
    • And TBig can be converted to TSmall
    • the conversion is done and the output is TSmall.

If it was the contrary (as if it were contravariant):

//a real instance that outputs TSmall
Outputter<TSmall> smallOutputter = new Outputter<TSmall>();

//just a view of smallOutputter
ICanOutput<TBig> bigOutputter = smallOutputter;
  • smallOutputter.getAnInstance() will return TSmall
  • And because bigOutputter was assigned with smallOutputter:
    • internally, bigOutputter.getAnInstance() will return TSmall
    • But TSmall cannot be converted to TBig!!
    • This then is not possible.

This is why "contravariant" types cannot be used as output types


What you can do with "Contravariant"?

Following the same idea above, contravariant uses the modifier in, meaning that the type can be an input parameter of a method, but not an output parameter.

Suppose you have these class and interface:

interface ICanInput<in T> { bool isInstanceCool(T instance); }

class Analyser<T> : ICanInput<T>
{
    bool isInstanceCool(T instance) { return instance.amICool(); }
}

Again, suppose the types TBig inheriting TSmall. This means that TBig can do everything that TSmall does (it has all TSmall members and more). But TSmall cannot do everything TBig does (TBig has more members).

When you do this (a classic contravariant assignment):

//a real instance that can use TSmall methods
Analyser<TSmall> smallAnalyser = new Analyser<TSmall>();
    //this means that TSmall implements amICool

//just a view of smallAnalyser
ICanInput<TBig> bigAnalyser = smallAnalyser;
  • smallAnalyser.isInstanceCool:
    • smallAnalyser.isInstanceCool(smallInstance) can use the methods in smallInstance
    • smallAnalyser.isInstanceCool(bigInstance) can also use the methods (it's looking only at the TSmall part of TBig)
  • And since bigAnalyser was assigned with smallAnalyer:
    • it's totally ok to call bigAnalyser.isInstanceCool(bigInstance)

If it was the contrary (as if it were covariant):

//a real instance that can use TBig methods
Analyser<TBig> bigAnalyser = new Analyser<TBig>();
    //this means that TBig has amICool, but not necessarily that TSmall has it    

//just a view of bigAnalyser
ICanInput<TSmall> smallAnalyser = bigAnalyser;
  • For bigAnalyser.isInstanceCool:
    • bigAnalyser.isInstanceCool(bigInstance) can use the methods in bigInstance
    • but bigAnalyser.isInstanceCool(smallInstance) cannot find TBig methods in TSmall!!! And it's not guaranteed that this smallInstance is even a TBig converted.
  • And since smallAnalyser was assigned with bigAnalyser:
    • calling smallAnalyser.isInstanceCool(smallInstance) will try to find TBig methods in the instance
    • and it may not find the TBig methods, because this smallInstance may not be a TBig instance.

This is why "covariant" types cannot be used as input parameters


Joining both

Now, what happens when you add two "cannots" together?

  • Cannot this + cannot that = cannot anything

What could you do?

I haven't tested this (yet... I'm thinking if I'll have a reason to do this), but it seems to be ok, provided you know you will have some limitations.

If you have a clear separation of the methods that only output the desired type and methods that only take it as an input parameter, you can implement your class with two interfaces.

  • One interface using in and having only methods that don't output T
  • Another interface using out having only methods that don't take T as input

Use each interface at the required situation, but don't try to assign one to another.

Daniel Möller
  • 84,878
  • 18
  • 192
  • 214
0

Generic type parameters cannot be both covariant and contravariant.

Why? This has to do with the restrictions which in and out modifiers impose. If we wanted to make our generic type parameter both covariant and contravariant, we would basically say:

  • None of the methods of our interface returns T
  • None of the methods of our interface accepts T

Which would essentially make our generic interface non-generic.

I explained it in detail under another question:

Andrzej Gis
  • 13,706
  • 14
  • 86
  • 130