Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 8 / c / Solution 2026-10-31
View more
Store the minimal elements of the finite generating set. The represented upper set itself may be infinite; the code manipulates its finite basis.
class UpSet[T <: Ordered[T]](c: Set[T]) extends Ordered[UpSet[T]] {
  private val basis: Set[T] = minimal(c)
  def contains(x: T): Boolean = basis.exists(a => a <= x)
  def intersection(that: UpSet[T]): UpSet[T] = {
    val generators: Set[T] =
      for (a <- basis; b <- that.basis) yield a.lub(b)
    new UpSet[T](generators)
  }
  def <=(that: UpSet[T]): Boolean = basis.forall(a => that.contains(a))
  def lub(that: UpSet[T]): UpSet[T] =
    new UpSet[T](basis union that.basis)
}
The abstraction function and representation invariant are
(1)
Removing nonminimal generators preserves the upward closure: in a finite generating set, repeatedly descending below any discarded element must reach a retained minimal element. Thus the constructor represents exactly the required finitely generated upper set.
Membership follows directly from the abstraction function. For intersection, an element lies above some and some exactly when it lies above their least upper bound:
(2)
The forward implication is the defining leastness property; the reverse uses that is an upper bound and transitivity. Consequently
(3)
Recomputing minimal elements therefore yields a finite basis for the exact intersection.
For subset inclusion, it suffices that every generator of the left-hand upper set belongs to the right-hand upper set. Necessity holds because each generator belongs to its own closure by reflexivity. Sufficiency holds because the right-hand set is upward closed. Finally,
(4)
Thus lub computes union, which is the least upper bound under subset inclusion. The empty basis represents the empty set; all four methods handle it without a special case. As in part (a), two distinct Scala objects may denote the same abstract ordered value. Retaining several equivalent representatives is harmless: they generate the same upward closure, and the strict-comparison test removes only genuinely nonminimal values.
Read the full article