Represent a multiset by a pure multiplicity function. Every operation returns a new function describing updated counts:An empty instance is
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))
}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 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 positively and fail the variance-position rule. Introduce : 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.[ref]Scala 2.11 basic declarations and definitions specification. Type Parameters, Variance Annotations; bounds and sign changes
Pointwise evaluation givesNo 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. Articles by others on the same topic
There are currently no matching articles.