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.
Use pattern matching and an optional value to distinguish absence from a present result:
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(x: T, y: U): PartialFn[T, U] =
    new PartialFn[T, U]((x, y) ::
      data.filterNot { case (key, _) => key == x })
}
The representation precondition is that equal keys always have equal associated values, with a stable equality relation on keys. This permits harmless repeated identical pairs; it excludes conflicting outputs for one input. get therefore returns Some(y) exactly when the represented partial function is defined at x. Removing filters out every occurrence of the key and leaves all other pairs unchanged. Adding first removes every old occurrence and prepends exactly the new pair, proving the partial function update postcondition even if the input contains duplicate identical pairs. The immutable linked list representation leaves the original mapping unchanged. Each operation has worst-case time complexity for pairs under constant-cost key equality.
The second partial function accepts this one's outputs. Put this method inside the invariant class in part (b):
def compose[V](that: PartialFn[U, V]): PartialFn[T, V] = {
  val pairs: List[(T, V)] = data.flatMap {
    case (x, y) => that.get(y).map(z => (x, z)).toList
  }
  new PartialFn[T, V](pairs)
}
The represented mapping is , since the paper explicitly applies that second despite the method name. A pair is emitted exactly when this mapping supplies a y and that.get(y) supplies a z. Hence its domain of a partial function is and its value there is . This is strict composition of partial functions: either missing stage makes the composite undefined. Repeated equal input pairs still produce the same output, preserving the representation invariant. With and pairs, direct association-list lookup gives worst-case time complexity, not a hidden constant-cost dictionary lookup.
A covariant type parameter preserves subtyping: if , then PartialFn[T,A] <: PartialFn[T,B] when its second parameter is covariant. In Scala the class annotation is +U. A mapping that produces a narrower output can be used where a broader output is expected. Covariance describes a type relationship; it does not convert stored values or make mutation through a widened reference safe.[ref]
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]

Ancestors (10)

  1. Imperative programming
  2. 2018
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version