3

In many OOP programming languages, types can be made co-, contra- or in- variant. Most (if not all of these languages) are able to let variables be mutated in place, i.e. they are not fully immutable languages.

I've seen in this SO answer that, in Scala at least, neither a covariant type can appear in a contravariant position nor a contravariant type can appear in a covariant position.

The problem I have with this answer (and in fact with all similar examples I ever found on the internet) is that it relies on mutability to show evidence of the above fact.

So my questions are:

  • does even the concept of variance make sense in an immutable environment?
  • if so, then could every type of a speculative fully immutable OOP language (like, all of them) be made covariant, regardless of where they are used (i.e. as function input types / function output types)?
Improve this question
8
  • 1
    Wouldn't lack of variance imply an invariant type?
    – Robert Harvey
    Sep 23, 2019 at 14:36
  • To my understanding, "lack of variance" is the definition of type invariance -- that is not covariant nor contravariant.
    – ljleb
    Sep 23, 2019 at 14:46
  • 4
    The mutability in those examples is a red herring. They are just an intuitive way to show how wrong variance could be unsound. You get the same problems when you cast immutable containers or functions around. However, most functional languages do not feature subtyping and therefore don't need a concept of variance.
    – amon
    Sep 23, 2019 at 15:02
  • @amon "You get the same problems when you cast immutable containers or functions around": Hmm I'm not sure about this. Could you please write an answer with an example or a proof that supports this fact? You would answer all of my questions at the same time. :)
    – ljleb
    Sep 23, 2019 at 15:11
  • @amon "most functional languages do not feature subtyping" - really? What languages are you thinking of?
    – Bergi
    Sep 24, 2019 at 0:49

3 Answers 3

Reset to default
9

does even the concept of variance make sense in an immutable environment?

Yes; presence of subtyping is independent of immutability.

could every type of a speculative fully immutable OOP language (like, all of them) be made covariant, regardless of where they are used (i.e. as function input types / function output types)?

As a simple demonstration why function input types can't be covariant, with no mutability involved (using Scala syntax):

val f: Int => Int = x => 2 * x
val g: Any => Int = f  // allowed by covariance
g("")  // what should this do?

The rule is still the same: "producer extends (covariant), consumer super (contravariant)". And a function is a consumer of its input type.

Improve this answer
1
  • I was actually writing my own answer accordingly to the one written by JimmyJames, in almost exactly this format, when you posted it. Sometimes coincidences can be disappointing.
    – ljleb
    Sep 23, 2019 at 17:03
11

Variance has nothing to do with mutability. It appears at the intersection of parametric polymorphism and subtyping.

The oldest example of variance is actually an example that comes out of functional programming, namely the question: when is a function type a subtype of another function type?

And it turns out that a function type is a subtype of another function type if its inputs are at least as general and its outputs at least as specific as the supertype.

In other words, functions are contravariant in their inputs and covariant in their outputs.

Improve this answer
1
1

Suppose you have a function that takes a list/array and a comparison function and returns a new one with the items sorted. If I have a list of Integers objects, I need a function that can sort integers: compare(a,b). With variance-free typing, I either have to specify that the function must take integers compare(a: Integer, a:Integer) or that it must take a specific super-type of integer e.g. compare(a: Object, a:Object). But what if I have a comparison defined as compare(a: Number, b: Number)? It should work fine but I can't use it in either case. So we need to be able to specify that the comparison function needs to be able to handle Integer or any superclass of Integer i.e. contra-variance.

Improve this answer
6
  • Just to be sure, in your example compare(a: Number, b: Number), is Number assumed to not be a supertype of Integer?
    – ljleb
    Sep 23, 2019 at 16:03
  • Number is assumed to be a superclass of Integer.
    – JimmyJames
    Sep 23, 2019 at 16:15
  • I'm not sure then why compare(a: Number, b: Number) would not work where compare(a: Object, b: Object) would. Also, I'm not sure what you mean by "It should work fine but I can't use it in either case", maybe that's what I'm missing?
    – ljleb
    Sep 23, 2019 at 16:17
  • A comparison function defined as compare(a: Object, b:Object) must be able to compare any two objects e.g. two Strings or a String and a List. compare(a: Number, b: Number) doesn't accept Strings or Lists.
    – JimmyJames
    Sep 23, 2019 at 16:23
  • Sorry, I meant in the context of an Integer application, which I thought was what you meant in your answer. So lets say we have sort(c: OrderedCollection[Integer], compare: (T, T) => T), then as long as T is a supertype of Integer there is no type error. Outside of this context, then indeed you seem to be right. Anyways, even if not everything was clear to me in your answer, I got a clear answer to my questions.
    – ljleb
    Sep 23, 2019 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.