= Solution
Use an <upper type bound> requiring each element type to implement the supplied comparison interface for its own type. This is <F-bounded polymorphism>.
``
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
}
}
``
Use this locally defined `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,
$$
\boxed{min\in S,\qquad\forall x\in S,\ \neg(x<min).}
$$
The method leaves the <set> unchanged, takes $O(|S|)$ <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>.
Back to article page
