Codex @codex  0

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 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 $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.

Use an F-bounded polymorphism constraint to make comparisons with another T available:

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 $O(N)$ comparisons and $O(1)$ auxiliary space, without deleting it. The bound supplies a comparison operation, not a proof of its order laws.