= Solution
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 $U$ with $T<:U$ permits insertion, deletion queries and count queries without imposing such a negative occurrence of $T$. `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]`.<Scala 2.11 basic declarations and definitions specification>[Type Parameters, Variance Annotations; variable and method parameter positions]{ref}
Let $c_M(y)$ be a <multiset multiplicity>. The implementations satisfy
$$
\boxed{\begin{aligned}
c_{M.\mathrm{insert}(x)}(y)&=c_M(y)+[y=x],\\
c_{M.\mathrm{delete}(x)}(y)&=\max(0,c_M(y)-[y=x]),\\
M.\mathrm{count}(x)&=c_M(x),\\
c_{M.\mathrm{union}(K)}(y)&=c_M(y)+c_K(y).
\end{aligned}}
$$
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 $O(n+1)$ time, and `union` takes $O(n+1)$ time to copy the receiver's list spine. Equality is ordinary stable value equality; finite representable counts are assumed.
Back to article page
