Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 8

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)
}

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))
}