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)?
ljleb
  • 41
  • 6
  • 1
    Wouldn't lack of variance imply an *invariant* type? – Robert Harvey Sep 23 '19 at 14:36
  • To my understanding, "lack of variance" is the definition of type invariance -- that is not covariant nor contravariant. – ljleb Sep 23 '19 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 '19 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 '19 at 15:11
  • @amon "*most functional languages do not feature subtyping*" - really? What languages are you thinking of? – Bergi Sep 24 '19 at 00:49
  • @Bergi SML, Haskell, Rust are examples of languages without subtyping. The typeclasses/traits in these languages are just type constraints, not supertypes. Of course even more languages combine FP with OOP and do support subtyping, e.g. OCaml or Scala. – amon Sep 24 '19 at 07:49
  • @amon In Haskell, `a -> a` is a subtype of `a -> b`. Similarly for functions in SML or Rust, and those also have subtyping for [module signatures](https://en.wikipedia.org/wiki/Standard_ML#Module_system) or [lifetimes](https://doc.rust-lang.org/nomicon/subtyping.html). – Bergi Sep 24 '19 at 08:57
  • @Bergi that is a valid standpoint, but at this point we would need a proper definition for subtyping. Counterpoints: modules are not types, and therefore aren't subtypes. Parametric polymorphism may indicate that a function signature is compatible in some places, but because those type parameters will at some point get instantiated with concrete types they are not compatible in general. Good point about Rust lifetimes. – amon Sep 25 '19 at 20:36

3 Answers3

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.

Jörg W Mittag
  • 101,921
  • 24
  • 218
  • 318
  • 1
    this is my go to explanation of how functions flip variance on output http://blog.ezyang.com/2014/11/tomatoes-are-a-subtype-of-vegetables/ – jk. Sep 24 '19 at 07:19
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.

Alexey Romanov
  • 1,467
  • 11
  • 15
  • 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 '19 at 17:03
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.

JimmyJames
  • 24,682
  • 2
  • 50
  • 92
  • 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 '19 at 16:03
  • Number *is* assumed to be a superclass of Integer. – JimmyJames Sep 23 '19 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 '19 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 '19 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 '19 at 16:33
  • I think maybe you are missing that the compare function isn't always necessarily a lambda. It could be an existing function defined in a library, for example. Lambda are a special case where the argument type is defined by it's context. – JimmyJames Sep 23 '19 at 17:56