F-bounded polymorphism 2026-10-31
A type parameter can be bounded using a type expression containing that same parameter. In Scala, [T <: Ordered[T]] requires each admissible T to provide comparison with another T. This gives a generic minimum scan access to x < y for two elements of type T. An arbitrary unrelated upper bound would not establish the needed argument type.
Generic method 2026-10-31
An object method with its own type parameters, instantiated or inferred at each call. In Scala, def identity[T](x: T): T = x is a generic method. A method def accept(x: T) inside class Box[T] instead uses a class type parameter fixed by the receiver's type argument; it is not itself a generic method with a separately chosen T on every call. This distinction matters in method overloading.
Immutable object 2026-10-24
An immutable object does not change its observable state after construction. Immutable fields prevent reassignment of their stored values, but fields containing references to mutable software objects do not automatically make the reachable software object graph immutable. Read-only generic producers can often support covariant type parameters; publicly writable fields generally cannot.
Mutual recursion 2026-10-31
Two or more functions are mutually recursive when their definitions call one another in a cycle. Two algebraic data types can likewise be mutually recursive when constructors of each refer to the other. For alternating sequences Zig a b and Zag b a, descending one constructor exchanges the type parameters; a pair of mapping functions must exchange its arguments correspondingly. A mutually recursive fold may have two independent result types : its handlers have types a -> s -> r and b -> r -> s, with empty results of types r and s. Equality of the two result types is not required by type inference.
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,
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.
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]
The input-key representation invariant and the partial function semantics are unchanged.
Because Set is invariant in the specified Scala library, even returning Set[U] would place the class's covariant type parameter in an invariant position. Introduce a fresh widened type for each lifting.
class CoPartialFnExt[T,+U](data: List[(T,U)])
    extends CoPartialFn[T,U](data) {

  def forwardLift[V >: U](s: Set[T]): Set[V] = {
    val ys: List[V] = this.data.collect {
      case (x,y) if s.contains(x) => y
    }
    ys.toSet
  }

  def backwardLift[V >: U](s: Set[V]): Set[T] =
    this.data.collect {
      case (x,y) if s.contains(y) => x
    }.toSet
}
The lower type bound gives , so stored output values can be widened into List[V] or passed to s.contains. Both exposed Set types use invariant method type parameters, not the class's U. Calling forwardLift[U] or backwardLift[U] when the concrete output type is known recovers the exact output universe; a broader admissible universe is also safe.
For a partial function, the forward formula is understood only for inputs in its domain of a function. The implementations therefore compute
The conversion to a set removes repeated images. Inputs not in the domain of a function contribute nothing to either lifting.
Only the first constructor needs to be inspected:
headZig :: Zig a b -> a
headZig (Cins x _) = x
headZig Nil = error "headZig: empty input"

headZag :: Zag a b -> a
headZag (Cans x _) = x
headZag Nal = error "headZag: empty input"
The first type parameter is the type of the first element in either algebraic data type. The source examples therefore return 1 and "C", respectively. These functions are partial at empty inputs, as allowed by the stated nonempty-input requirement.
The constructors ZigType and ZagType record which of the two alternating positions contains the last element. The tail types swap the two type parameters, so the return type of lastZag swaps them back:
lastZig :: Zig a b -> ZigOrZagType a b
lastZig Nil = error "lastZig: empty input"
lastZig (Cins x Nal) = ZigType x
lastZig (Cins _ zs) = lastZag zs

lastZag :: Zag a b -> ZigOrZagType b a
lastZag Nal = error "lastZag: empty input"
lastZag (Cans x Nil) = ZagType x
lastZag (Cans _ zs) = lastZig zs
For example, lastZig passes a tail of type Zag b a to lastZag, whose result then has type ZigOrZagType a b, exactly as required. Conversely, lastZag passes a Zig b a tail to lastZig. A singleton returns its element in the appropriate constructor; a longer input discards one element and uses mutual recursion on the shorter tail. This proves correctness by structural induction on the finite alternating sequence. The three source examples give ZigType 2, ZagType "D", and ZigType True.
The standard output is three lines:
A
2.3
B
This is program output, excluding any interactive interpreter's display of returned values. The calls a.m(1) and b.m(5.6) compute squares without printing. In A, the concrete m(Int) wins over the generic method at argument 1; the string and 2.3 use m[T] and print their arguments.
For b: B[Any], the class type parameter has already become Any, so the two alternatives are m(Any) and m(Double), rather than a method with its own freely inferred type parameter. The Double alternative is more specific. It accepts 4 by numeric widening, so b.m(4) computes 16.0 without printing; b.m("B") prints B; b.m(5.6) computes a square without printing. These are applications of the Scala 2.11 method overloading rules, with the arithmetic return values discarded in statement position.[ref]
The output is 1, with no newline. The Any in class B[Any] and class C[Any] is a type parameter name that shadows the standard type scala.Any inside those class bodies. Renaming it to T preserves the program's meaning. Thus new B[Int] has an inherited m(Double) and its own m(Int); obj1.m(1) selects the latter and prints 1. The call with 2.3 can only use the inherited m(Double), which computes a sum without printing.
For new C[Any], the supplied type argument is the standard scala.Any, so the overloads are m(Double) and m(scala.Any). The more-specific Double alternative accepts 4 by numeric widening, and accepts 5.6 directly. Both return sums without printing. A computed result is not automatically screen output. This reasoning uses the Scala 2.11 overload conventions of Question 5(a); type erasure does not turn either class's generic-argument overload into an method overriding of m(Double).
With subtype polymorphism, a trait or abstract class declares an operation and concrete subclasses implement or override it. A Player reference holding a House object invokes House.play through dynamic dispatch. The client is written against the common contract.
With parametric polymorphism, a software class or generic method has a type parameter, such as List[T] or def identity[T](x: T): T = x. The same definition works for many supplied type arguments, with static relationships between input and output types. Method overloading is another mechanism, usually called ad hoc polymorphism: alternatives share a name but are selected from their parameter signatures at compile time.
The output is BADDCD, without a newline. Method overloading chooses a signature using static types, including the instantiated class type parameter; numeric widening can make a Double parameter applicable to an Int argument.
  • a.m(o1) chooses m(Int), which is more specific than the polymorphic method: B.
  • a.m(o2) uses m[Double](Double): A.
  • b.m(o1) compares m(Any) and m(Double). Int can widen to Double, and Double is more specific than Any: D.
  • b.m(o2) chooses m(Double) over m(Any): D.
  • c.m(o1) compares the instantiated m(Int) with m(Double) and chooses m(Int): C.
  • c.m(o2) can use only m(Double): D.
The third call is the subtle one: the existence of m(Any) does not prevent the more specific numeric overload from winning. These are Scala 2 method overloading and numeric widening rules. [ref]
Tree is a type constructor, taking the element type parameter a to the algebraic data type Tree a. It is not a value and has no ordinary value-level function type; its kind of a type is * -> *. The other names are data constructors with polymorphic type signatures:
One :: a -> Tree a
Two :: Tree a -> Tree a -> Tree a
One constructs a leaf-labelled binary tree with one leaf; Two joins two such trees under a new internal node. Unlike a general binary tree representation with empty child slots, this representation has no empty tree.[ref]
Programming language polymorphism means that one interface or program definition can be used with values of multiple types. In object-oriented programming, subtype polymorphism allows references with a common static type to denote instances of different concrete subclasses or implementers of a trait. An object method call uses dynamic dispatch to select the overriding implementation belonging to the receiver's runtime type. For example, different implementations of a playlist interface can respond to the same insert call without the client testing their concrete classes.
Parametric polymorphism uses type parameters, as in Sequence[A], so the same definition works uniformly for songs, integers, or other elements. Ad hoc polymorphism includes method overloading, where different parameter signatures share a name and the static types determine overload selection. These mechanisms are distinct: selecting an overloaded signature is not the same step as dispatching an override of that selected signature. Class inheritance can supply implementations, but the reusable interface and legal subtyping relationship determine what a polymorphic client may do.
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]
Subtype polymorphism lets a reference with a common supertype denote values of different implementing classes. A call through that reference uses dynamic dispatch to select the concrete implementation.
Parametric polymorphism defines an operation or data structure using type parameters, such as a collection with an element-type parameter. Instantiations retain type information while reusing one generic definition.
Ad hoc polymorphism, commonly expressed by method overloading, gives several implementations the same name but different parameter signatures. The compiler selects a suitable overload using the available static types. This selection differs from later dynamic dispatch on the receiver of a selected instance method. A programming language can support all three in one program.
Instantiate the two type parameters and implement the function object interface:
val square: Fun[Int, Int] = new Fun[Int, Int] {
  override def apply(x: Int): Int = x * x
}
Parametric polymorphism occurs because the generic trait is specialized by choosing its argument and result types. Subtype polymorphism occurs because the anonymous implementing software class is used through a Fun[Int, Int] reference; calls to its apply operation use the object interface contract and dynamic dispatch. Multiplication itself is not the second polymorphism needed for this explanation.
For values whose mathematical squares fit in a signed 32-bit integer, the result is the ordinary square. Outside that range, the supplied integer return type cannot represent every mathematical square, and the multiplication follows Scala integer-overflow behavior. An implementation requiring exact mathematical results for all integer inputs would need a wider result type or an explicit overflow exception.
Give the two components independent upper type bounds and immutable fields:
final case class BoundedPair[+A <: Base, +B <: Base](first: A, second: B)
Each component type must be a subtype of Base, but the two need not be the same subtype. The pair's fields cannot be reassigned. Their read-only use permits covariant type parameters; the separate upper type bounds constrain admissible instantiations.[ref]
The component accessors retain their precise static types. For example, a BoundedPair[Derived, Base] exposes its first component as Derived, so derived-specific operations are available without a cast. A pair whose two fields are simply declared Base discards that distinction. Immutability here concerns the two stored references; it does not guarantee that the referenced software objects have immutable internal state.
The “Variance Annotations” section specifies variance positions and lower-bound widening, used when an immutable class's output type parameter is covariant while a method must accept a possibly broader output value.