First-class functions: Why should input types be counter-variants?

Question

To demonstrate the problem I will use Scala code (although this is a rule formalized by Luca Cardelli).

trait Function1[-A, +R] {
  def apply(x: A): R
}

In Scala this means that a function with an element is contravariant in the input and covariant in the output.

That is, we can only consider that a function f: (X => Y) is a subtype of a function g: (X' => Y') if X for a supertype of X' and Y for a subtype of Y'.

Why does this happen?

Answer 1

The justification for the type of entry being contravariant [and output, covariant] is to satisfy the Principle of Liskov’s replacement. This principle states that "subclasses should always be less restricted than their superclasses". In other words, where a base class object could be used, a subclass object could also be used.

So if we have a legacy code that calls a method foo base class, passing through Bar as parameter and receiving Baz, and this method is overwritten (and not only overloaded) in the subclasses, it is necessary that they:

1. Accept at least Bar as argument; they can accept plus that Bar, but not less. If a subclass decides to accept, for example, anything (i.e. Object), no problem: because she will still be accepting Bar.

   As any superclass of Bar meets this requirement, the type of the input parameter is variant.

2. Return an object compatible with Baz; they can return something more specific that Baz, but not something incompatible with it (i.e. which has a more restricted interface, missing fields/methods, etc). As objects of subclasses can be used in place of base class objects (by the Liskov principle itself), they can be used as return value (i.e. the output type is covariant).

This decision [to use output covariance and countervariance in input] guarantees type security, reducing/eliminating type errors at runtime. Strategies more restricted (ex.: invariance) also have the same effect, but without the convenience of customizing the behavior of subclasses as needed.

It is also worth mentioning that there are languages (such as Eiffel) that support covariant input types. This strategy can be convenient in many situations, even if it is not 100% fail-safe. Example (using Java syntax - more familiar than Eiffel’s):

class AbrigoAnimais {
    void adicionarAnimal(Animal a) { ... }
    Animal obterAnimal() { ... }
}

class AbrigoGatos extends AbrigoAnimais {
    void adicionarAnimal(Gato g) { ... }  // Entrada covariante (não typesafe)
    Gato obterAnimal() { ... }            // Saída covariante (typesafe)
}

AbrigoGatos abrigo = new AbrigoGatos();
// Erro em tempo de compilação
abrigo.adicionarAnimal(new Cachorro());
// Erro em tempo de execução
((AbrigoAnimais)abrigo).adicionarAnimal(new Cachorro());

Answer 2

My (pragmatic) answer to the question:

The reason it is only safe to return a subtype of the return type of the original function (+R) it is clear by analyzing a concrete case:

whereas Gato is a subtype of Animal.

class Gato extends Animal

Note the following example where f <: g :

g: (Int => Animal) 
f: (Int => Gato)

It is clear that in order to use f in place of g, f needs to return a subtype of R, i and.., Gato <: Animal; otherwise f could return a type out of compliance with the signature of g (a guy who wasn’t a Animal).

The opposite rule (-A) can be understood by another practical example in which f <: g:

g: (Gato => Int) 
f: (Animal => Int)

It is clear that in order to use f in place of g, f needs to receive a supertype of A, i and.., Animal >: Gato; otherwise f could receive a type out of compliance with the signature of g. (there is no problem in f also meet other subtypes of Animal, provided that Gato be one of them to satisfy the G).

P.S.: This second part may sound a little strange to Java programmers, since the language does not allow one method to be overwritten by another with broader type arguments. This was a language decision (which Scala also embraced, functions and methods are two different things); the most likely reason for the decision is that allowing this type of superscript along with the ability to overload would bring a number of complications to the language (more information on SOE).