Lower type bound 2026-10-31
View more
A lower bound requires an admissible type argument to be a supertype of a specified type. In Scala, [V >: U] means . For an immutable software class covariant in U, a method accepting a new output value cannot consume U directly in a contravariant method-parameter position. Instead, add[V >: U](x: V) accepts a possibly wider value and returns a fresh instance parameterized by V. The original narrower instance remains unchanged. The variance-position rule and subtyping justify this widening; a bound alone does not authorize mutating an existing instance through a widened reference.[ref]
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 8 / c / Solution 2026-10-31
View more
An immutable object can widen its element type when adding a value by returning a new object. Introduce a lower type bound on the method's fresh type parameter.
class ISet[+T](contents: List[T]) {
  private val elems: List[T] = contents.distinct

  def add[U >: T](x: U): ISet[U] = {
    val widened: List[U] = elems
    if (widened.contains(x)) new ISet[U](widened)
    else new ISet[U](x :: widened)
  }

  def delete(): (T, ISet[T]) = {
    require(elems.nonEmpty)
    (elems.head, new ISet[T](elems.tail))
  }
}
As before, the representation invariant excludes duplicates, and the abstraction function returns the unordered set of entries. The constructor normalization makes the representation invariant hold even for repeated initial entries. Both operations construct a fresh set object and leave the original object unchanged, including when addition finds an existing member.
For a receiver representing , the new object returned by add represents . Deletion returns a pair with and representing . Crucially,
(1)
The widened list is valid because immutable List itself has a covariant type parameter. A client can view an ISet[Int] as ISet[Any], but adding a string creates a separate widened result; it cannot put a string into the old integer set. This explains how using immutable objects makes the desired type variance sound. A direct add(x: T) on a covariant software class would still violate the variance-position rule; immutability alone does not repair an incorrectly typed method signature.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 6 / b / Solution 2026-10-31
View more
A covariant type parameter may be produced but not consumed directly. Widen the output type of add through a lower type bound. In compose, the first parameter of CoPartialFn is invariant, so replace its occurrence of U by a fresh type parameter W with lower type bound U.
class CoPartialFn[T,+U](val data: List[(T,U)]) {
  require(data.map(_._1).distinct.size == data.size)

  def get(x: T): Option[U] =
    data.find(p => p._1 == x).map(_._2)

  def add[V >: U](x: T, y: V): CoPartialFn[T,V] = {
    val old: List[(T,V)] = data.filterNot(p => p._1 == x)
    new CoPartialFn[T,V]((x,y) :: old)
  }

  def remove(x: T): CoPartialFn[T,U] =
    new CoPartialFn[T,U](data.filterNot(p => p._1 == x))

  def compose[V, W >: U](that: CoPartialFn[W,V]): CoPartialFn[T,V] = {
    val pairs: List[(T,V)] = data.flatMap { case (x,y) =>
      that.get(y).toList.map(z => (x,z))
    }
    new CoPartialFn[T,V](pairs)
  }
}
List, Tuple2, and Option are covariant in their element/output parameters, so data, get, and remove are valid producers. The variance-position rule permits U in the lower type bounds; every value of U can be passed to that.get, since . No cast or mutation through a widened reference is needed.[ref]
(1)
The input-key representation invariant and the partial function semantics are unchanged.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 8 / b / Solution 2026-10-31
View more
Represent a multiset by a pure multiplicity function. Every operation returns a new function describing updated counts:
class ContraMSet[-T](f: T => Int) {
  def count(x: T): Int = f(x)

  def insert(x: T): ContraMSet[T] =
    new ContraMSet[T]((y: T) => f(y) + (if (y == x) 1 else 0))

  def delete(x: T): ContraMSet[T] =
    new ContraMSet[T]((y: T) => {
      val old = f(y)
      if (y == x && old > 0) old - 1 else old
    })

  def union[U <: T](that: ContraMSet[U]): ContraMSet[U] =
    new ContraMSet[U]((y: U) => this.count(y) + that.count(y))
}
An empty instance is new ContraMSet[T]((_: T) => 0). The constructor's precondition is that f is pure and gives a nonnegative integer count, with finite support of a multiset if only finite multisets are intended. Nonnegativity and the support condition are preserved by each operation. Integer overflow must be excluded for this fixed-width count interface.
A contravariant type parameter makes ContraMSet[T] a consumer of values of type T. Thus a counter able to answer queries for every animal can also answer queries restricted to cats. It does not expose or enumerate stored T values. The return type ContraMSet[T] is legal: its outer covariant result position and the class's contravariant argument position together place negatively.
For union, the argument itself is in a negative position, while its ContraMSet argument would reverse that sign. Using ContraMSet[T] directly as the parameter type would therefore put positively and fail the variance-position rule. Introduce : both operands can count every U, and their sum is a ContraMSet[U]. This is a restriction to a common query domain; operations do not promise to preserve counts outside the narrowed domain.[ref]
Pointwise evaluation gives
(1)
No old function is modified, so updates preserve immutable object. Constructing each wrapper takes constant work, but a later count may traverse a chain of previously created programming closures; its running time need not be constant in the history length. This functional representation trades enumeration and direct storage of occurrences for composable counting behavior.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 8 / b / Solution 2026-10-31
View more
Hypothetical covariance would allow the following unsound alias:
val narrow: MSet[Int] = new MSet[Int](Nil)
val wide: MSet[Any] = narrow       // hypothetical covariant conversion
wide.add("not an integer")
val n: Int = narrow.delete()      // would return the inserted string
The last value cannot satisfy its promised type. This is the covariance failure for a mutable collection: a broader consuming interface could insert values that violate a narrower alias's guarantee. The actual invariant MSet[T] rejects the conversion, and declaring +T while retaining add(x: T) is itself rejected by the variance-position rule. The mutable read-and-write interface must remain invariant in T.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 7 / e / Solution 2026-10-31
View more
Declare +U, keep its stored linked list immutable, and generalize operations that need to accept output values by a fresh lower type bound:
class PartialFn[T, +U](val data: List[(T, U)]) {
  def get(x: T): Option[U] =
    data.find { case (key, _) => key == x }.map(_._2)

  def remove(x: T): PartialFn[T, U] =
    new PartialFn[T, U](data.filterNot { case (key, _) => key == x })

  def add[V >: U](x: T, y: V): PartialFn[T, V] =
    new PartialFn[T, V]((x, y) ::
      data.filterNot { case (key, _) => key == x })

  def compose[V >: U, W](that: PartialFn[V, W]): PartialFn[T, W] = {
    val pairs: List[(T, W)] = data.flatMap {
      case (x, y) => that.get(y).map(z => (x, z)).toList
    }
    new PartialFn[T, W](pairs)
  }
}
get, remove, and the immutable val data expose U in covariant result positions: Scala's immutable List, Tuple2 and Option preserve that position. The old add(x:T,y:U) consumed U directly, violating the variance-position rule. The new add accepts a value of a chosen supertype V and returns a new mapping with that widened output type; it never inserts the wider value into the old narrower mapping.
The original compose also mentions U as the first, invariant parameter of PartialFn[U,V]. Changing only add is therefore insufficient. Its new first type parameter V >: U is independent of the class's covariant parameter except for the allowed lower bound. Any stored y:U is acceptable to that.get as a V, while the result has output type W. This lower type bound solution avoids unchecked variance annotations or casts. The official variance rules illustrate the same lower-bound widening technique for an immutable collection's consuming method; the later 2.13 text corroborates the rule, without identifying an installed 2018 compiler version.[ref]
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 8 / a / Solution 2026-10-25
View more
The maximally variant safe declarations are:
trait Rel1[+X, +Y] { val pairs: List[(X, Y)] }
trait Rel2[-X, +Y] { def relatives(x: X): List[Y] }
trait Rel3[-X, -Y] { def related(x: X, y: Y): Boolean }
Leaving one or both parameters invariant is also legal but admits fewer subtyping conversions. These are type variance annotations.
For Rel1, both parameters occur only as outputs. Scala's immutable List and Tuple2 are covariant, so a list of pairs of narrower types can safely be read as pairs of broader types. Thus both may be covariant type parameters. A contravariant declaration would permit, for example, treating a Rel1[Any, Int] containing (7, 0) as a Rel1[String, Int], then reading its first component as a String. That would be unsound; the compiler rejects the negative annotation at this output position.
For Rel2, X occurs as a method argument and therefore may be a contravariant type parameter; Y is returned in an immutable list and may be a covariant type parameter. A function that accepts every Any is safe to use where only String queries are issued. The opposite direction would be unsafe: if X were covariant, the following hypothetical conversion could call a string-only implementation with an integer:
val strings: Rel2[String, Int] = new Rel2[String, Int] {
  def relatives(x: String): List[Int] = List(x.length)
}
// Unsafe if Rel2 were incorrectly covariant in X:
// val arbitrary: Rel2[Any, Int] = strings
// arbitrary.relatives(7)
Making Y contravariant would instead allow an integer-valued Rel2[String, Any] to be read as a string-valued Rel2[String, String], recreating the output error.
For Rel3, both generic values are consumed and only a Boolean function result is produced, so both may be contravariant type parameters. A predicate accepting all values of broad types can answer queries restricted to narrower types. Covariance in either parameter would allow passing an unsupported value to a specialized implementation. For example, treating a string-only first-argument predicate as accepting Any would permit related(7, y) even though its body might call x.length. These are applications of the variance-position rule: method inputs reverse variance, whereas immutable outputs preserve it.[ref]
Read the full article