Represent the set by a private list containing each value once. Normalize the constructor input as well as checking future insertions; otherwise duplicate initial entries would violate the intended set behavior.The representation invariant is that
class Set[T](contents: List[T]) {
protected var elems: List[T] = contents.distinct
def add(x: T): Unit = {
if (!elems.contains(x)) elems = x :: elems
}
def delete(): T = {
require(elems.nonEmpty)
val x = elems.head
elems = elems.tail
x
}
}elems contains no duplicates under the chosen stable value equality; the abstraction function forgets its ordering and returns its set of elements. The protected field allows the subclass in part (d) to inspect its contents; that subclass is responsible for preserving the representation invariant if it mutates them.Insertion makes the represented set . Deletion requires , returns some , and leaves . ThusDeletion does not promise to choose a minimum. With this linked list representation, insertion takes time complexity because of its membership check, while deletion takes . Values should not mutate in a way that changes their equality while stored.
If the mutable set were allowed a covariant type parameter, both variables below could refer to the same mutable object:The broad view accepts any value, including a string. The narrow view still promises that deletion returns an
val s1: Set[Int] = new Set[Int](List())
val s2: Set[Any] = s1 // hypothetically permitted
s2.add("not an integer")
val n: Int = s1.delete() // cannot return an IntInt, yet the sole stored value is that string. This violates type safety:This is covariance failure for a mutable collection. The input occurrence in add(x: T) conflicts with the positive occurrence in the result of delete. Keeping a generic type invariance restriction prevents the unsafe aliasing. The example uses an initially empty set so that the problematic deletion result is forced.An immutable object can widen its element type when adding a value by returning a new object. Introduce a lower type bound on the method's fresh type parameter.As before, the representation invariant excludes duplicates, and the abstraction function returns the unordered set of entries. The constructor normalization makes the representation invariant hold even for repeated initial entries. Both operations construct a fresh set object and leave the original object unchanged, including when addition finds an existing member.
class ISet[+T](contents: List[T]) {
private val elems: List[T] = contents.distinct
def add[U >: T](x: U): ISet[U] = {
val widened: List[U] = elems
if (widened.contains(x)) new ISet[U](widened)
else new ISet[U](x :: widened)
}
def delete(): (T, ISet[T]) = {
require(elems.nonEmpty)
(elems.head, new ISet[T](elems.tail))
}
}For a receiver representing , the new object returned by
add represents . Deletion returns a pair with and representing . Crucially,The widened list is valid because immutable List itself has a covariant type parameter. A client can view an ISet[Int] as ISet[Any], but adding a string creates a separate widened result; it cannot put a string into the old integer set. This explains how using immutable objects makes the desired type variance sound. A direct add(x: T) on a covariant software class would still violate the variance-position rule; immutability alone does not repair an incorrectly typed method signature.Use an upper type bound requiring each element type to implement the supplied comparison interface for its own type. This is F-bounded polymorphism.Use this locally defined
trait Ordered[T] {
def <(that: T): Boolean
}
class MinSet[T <: Ordered[T]](contents: List[T])
extends Set[T](contents) {
def min: T = {
require(elems.nonEmpty)
var best = elems.head
var rest = elems.tail
while (rest.nonEmpty) {
if (rest.head < best) best = rest.head
rest = rest.tail
}
best
}
}Ordered, rather than silently substituting the standard library's different comparison interface. The type bound makes rest.head < best well typed. To interpret the result as a minimum, require the comparison to be a consistent strict total order; merely providing a method named < cannot establish its mathematical laws.The loop invariant is that
best is a minimum among the entries already inspected, and rest is exactly the uninspected suffix. Comparing its next head with best preserves that property. The loop variant is the length of rest. On termination,The method leaves the set unchanged, takes time complexity under constant-cost comparisons, and uses constant auxiliary space. It requires a nonempty set; inherited insertion and deletion continue to preserve the duplicate-free representation invariant. Articles by others on the same topic
There are currently no matching articles.