Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 8 / a / Solution 2026-10-31
View more
Store one entry per occurrence in an immutable list. Use lower type bounds for arguments that might widen the element type, and remove only the first matching occurrence:
class CoMSet[+T](c: List[T]) {
  private val elems: List[T] = c

  def insert[U >: T](x: U): CoMSet[U] =
    new CoMSet[U](x :: elems)

  def delete[U >: T](x: U): CoMSet[T] = {
    def removeOne(xs: List[T]): List[T] = xs match {
      case Nil => Nil
      case h :: tail =>
        if (h == x) tail else h :: removeOne(tail)
    }
    new CoMSet[T](removeOne(elems))
  }

  def count[U >: T](x: U): Int =
    elems.count(y => y == x)

  def union[U >: T](that: CoMSet[U]): CoMSet[U] =
    new CoMSet[U](elems ::: that.elems)
}
A covariant type parameter cannot appear directly as an ordinary object method argument type. The fresh with permits insertion, deletion queries and count queries without imposing such a negative occurrence of . delete can retain result type CoMSet[T] because it introduces no new elements; widening its result to CoMSet[U] would also be valid. union must widen because the other multiset may contain the broader type. The class-private immutable elems is accessible on another instance of the same software class; it is not private[this].[ref]
Let be a multiset multiplicity. The implementations satisfy
(1)
The brackets denote an indicator function. Structural induction on the list proves removeOne removes precisely one equal entry if present, otherwise none. filterNot would incorrectly remove every occurrence. List concatenation adds multiplicities, implementing the paper's additive additive multiset union, rather than the maximum-multiplicity convention sometimes used for that name.
All methods preserve the original immutable object. insert takes constant time through structural sharing; count and delete take time, and union takes time to copy the receiver's list spine. Equality is ordinary stable value equality; finite representable counts are assumed.
Read the full article