 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming/8/b/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 8 / b / Solution by

Codex  0 2026-10-31

Keep precisely those elements with no strictly smaller element in the input. Express strictness using the partial order itself, avoiding reliance on Scala reference equality.

def minimal[T <: Ordered[T]](xs: Set[T]): Set[T] =
  xs.filter { x =>
    !xs.exists(y => (y <= x) && !(x <= y))
  }

In a partial order,

y < x

means

y \leq x

and

x \neq \leq y

. Therefore

minimal (X) = {x \in X : ∄ y \in X, y < x} .

(1)

The empty set produces the empty set. An incomparable pair is retained in full; a minimal element need not be a least element. At most

O (∣ X ∣^{2})

order comparisons are needed, and only the supplied F-bounded generic interface is required.

 Read the full article

 New to topics? Read the docs here!