= Solution
Represent a <multiset> by a pure <multiplicity function>. Every operation returns a new <function> describing updated counts:
``
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))
}
``
An empty instance is `new ContraMSet[T]((_: T) => 0)`. The constructor's <precondition> is that `f` is pure and gives a nonnegative <integer> count, with finite <support of a multiset> if only finite <multisets> are intended. Nonnegativity and the support condition are preserved by each operation. <Integer overflow> must be excluded for this fixed-width count interface.
A <contravariant type parameter> makes `ContraMSet[T]` a consumer of values of type `T`. Thus a counter able to answer queries for every animal can also answer queries restricted to cats. It does not expose or enumerate stored `T` values. The <return type> `ContraMSet[T]` is legal: its outer covariant result position and the class's contravariant argument position together place $T$ negatively.
For `union`, the argument itself is in a negative position, while its `ContraMSet` argument would reverse that sign. Using `ContraMSet[T]` directly as the parameter type would therefore put $T$ positively and fail the <variance-position rule>. Introduce $U<:T$: both operands can count every `U`, and their sum is a `ContraMSet[U]`. This is a restriction to a common query domain; operations do not promise to preserve counts outside the narrowed domain.<Scala 2.11 basic declarations and definitions specification>[Type Parameters, Variance Annotations; bounds and sign changes]{ref}
Pointwise evaluation gives
$$
\boxed{f_{\mathrm{insert}(x)}(y)=f(y)+[y=x],\quad
f_{\mathrm{delete}(x)}(y)=\max(0,f(y)-[y=x]),\quad
f_{M\mathrm{\ union\ }K}(y)=f_M(y)+f_K(y).}
$$
No old <function> is modified, so updates preserve <immutable object>. Constructing each wrapper takes constant work, but a later `count` may traverse a chain of previously created <programming closures>; its <running time> need not be constant in the history length. This functional representation trades enumeration and direct storage of occurrences for composable counting behavior.
Back to article page
