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 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]
Pointwise evaluation gives
(1)
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.

Ancestors (11)

  1. 8
  2. Imperative programming (resit)
  3. 2015
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version