class MSet[T](contents: List[T]) {
protected var data: List[T] = contents
def add(x: T): Unit = {
data = x :: data
}
def delete(): T = data match {
case x :: xs => data = xs; x
case Nil => throw new NoSuchElementException("MSet.delete")
}
}The representation invariant interprets the list by its multiset of occurrences; order is immaterial and duplicates remain distinct occurrences.
add increases one multiplicity, while delete returns and removes one occurrence. The field is protected so the minimum-search subclass in part (d) can inspect it. Both successful updates take list operations. Deleting from an empty bag raises an explicit exception.Hypothetical covariance would allow the following unsound alias:
val narrow: MSet[Int] = new MSet[Int](Nil)
val wide: MSet[Any] = narrow // hypothetical covariant conversion
wide.add("not an integer")
val n: Int = narrow.delete() // would return the inserted stringThe last value cannot satisfy its promised type. This is the covariance failure for a mutable collection: a broader consuming interface could insert values that violate a narrower alias's guarantee. The actual invariant
MSet[T] rejects the conversion, and declaring +T while retaining add(x: T) is itself rejected by the variance-position rule. The mutable read-and-write interface must remain invariant in T.Use a lower type bound to widen the element type only in the new value:
class ISet[+T](contents: List[T]) {
private val data: List[T] = contents
def add[U >: T](x: U): ISet[U] =
new ISet[U](x :: data)
def delete(): (T, ISet[T]) = data match {
case x :: xs => (x, new ISet[T](xs))
case Nil => throw new NoSuchElementException("ISet.delete")
}
}The list is immutable and neither method changes this instance. A new wider value cannot be accepted directly as the old narrow
T; instead add[U >: T] returns a fresh ISet[U]. The original ISet[T] retains its element guarantee, and deletion returns both its old head and a fresh bag for the tail. This covariant persistent multiset safely shares unchanged list tails and preserves duplicate multiplicities. The historical name ISet does not require silently changing the question's bag semantics into duplicate-removing set semantics.[ref]Scala 2.13 variance annotations specification. Variance Annotations: lower-bound widening of Sequence.append
trait Ordered[T] {
def <(that: T): Boolean
}
class MinMSet[T <: Ordered[T]](contents: List[T])
extends MSet[T](contents) {
def min: T = {
if (data.isEmpty) throw new NoSuchElementException("MinMSet.min")
var best = data.head
var rest = data.tail
while (rest.nonEmpty) {
if (rest.head < best) best = rest.head
rest = rest.tail
}
best
}
}The upper type bound
T <: Ordered[T] guarantees the method signature needed for rest.head < best. Assuming that comparison implements the intended total ordering, the loop invariant says best is a minimum of the inspected prefix; the remaining suffix length decreases. The method returns a minimum in comparisons and auxiliary space, without deleting it. The bound supplies a comparison operation, not a proof of its order laws. Articles by others on the same topic
There are currently no matching articles.