Co- and Contravariance Part 2: Advanced Concepts

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:

  1. Input types: A <: C (input is contravariant)
  2. 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 overall
    • b 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) overall
    • c 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