This is the second part of our exploration into co- and contravariance. In part one, we covered the basic concepts and intuitions behind variance in type systems. Hopefully it already helped you to gain better understanding in the various co- and contravariance concepts. If you still struggle and change minusses to plusses or vice versa (or super to extend clauses) then this second part is for you.
Recap: Function Subtyping and Variance #
Before diving into advanced topics, let’s recap when one function can be substituted for another.
For functions
f :: a -> b
g :: c -> d
we say g <: f
(g is a subtype of f, meaning g can be used wherever f is required).
The subtyping relationship for functions follows these rules:
- Input types: A <: C (input is contravariant)
- Output types: D <: B (output is covariant)
This means:
- The subtype function must accept a supertype of what the original function accepts (parameters are contravariant)
- The subtype function must return a subtype of what the original function returns (return parameters are covariant)
Let’s also remember that in the Scala typesystem, contravariant types are denoted by a -
, and covariant types by a +
. We can also say a contravariant parameters are in a negative position and covariant parameters in a positive position.
We visualize this relationship with a simple graph:
f: A -------> B
^ | ^
| | |
| v |
g: C -------> D
Having said all this, we can turn towards higher order functions.
Functions with higher order functions as parameters #
Many programming languages use curried functions as their default style to write functions (haskell, idris, elm, purescript), other allow curried functions (Scala, typescript, javascript, F#). In curried functions there is no group of input parameters, instead parameters are resolved one by one and the result of this resolution is again a function.
Curried function types are e.g. written like this:
f :: a -> b -> c
Association and Variance Positions #
Interestingly, the notation a -> b -> c
is ambiguous regarding association. It could be parsed in two ways:
f :: (a -> b) -> c -- Function that takes a function as input
f :: a -> (b -> c) -- Function that returns a function as output
In most functional languages, the second interpretation (right association) is the default. But understanding both forms helps clarify variance positions.
Variance Positions in Nested Functions #
To understand variance positions in nested functions, we need to remember a key principle: variance flips in contravariant positions.
Let’s analyze both interpretations:
Left association: f :: (a -> b) -> c
- The parameter
(a -> b)
is in a contravariant (negative) position - Within this parameter:
a
is in a contravariant position relative to(a -> b)
, but since(a -> b)
is already contravariant,a
flips to a covariant (positive) position overallb
is in a covariant position relative to(a -> b)
, but flips to contravariant (negative) overall
c
is in a covariant (positive) position
| - | + |
| - +| |
f :: (a -> b) -> c
| + - | + |
Right association: f :: a -> (b -> c)
a
is in a contravariant (negative) position- The return value
(b -> c)
is in a covariant (positive) position - Within this return value:
b
is in a contravariant position relative to(b -> c)
, but remains contravariant (negative) overallc
is in a covariant position relative to(b -> c)
, and remains covariant (positive) overall
| - | + |
| | - + |
f :: a -> (b -> c)
| - | - + |
This pattern of alternating variance positions (often called the “variance dance”) becomes increasingly important when designing higher-order functions and interfaces with complex nested types.
Kommentare