This is the 14 June 2017 preliminary examination. All 38 printed subparts are answered. Source paper: released examination archive, member
a10098w1-2.pdf.Questions 1–4 use explicit pseudocode: array segments are half-open, a
var parameter can be reassigned in the caller, newly allocated cells are initialized by the code, and integer arithmetic is exact. Assume a radix at least two, finite valid acyclic linked lists, and a total ordering where keys are compared. Implementations with fixed-width temporary integers need a radix and bounds that avoid overflow. Questions 5–8 use the Scala 2 API style of the source, with separate namespaces for independent examples. Scala code is not claimed to have been compiled in the current environment.Allocate a fresh array and copy every digit:
function CopyNum(n: number): number
new(result, len(n))
for i := 0 to len(n)-1 do
result[i] := n[i]
return resultEvery coefficient in the digit-array integer representation is unchanged, so the value is unchanged. The new array shares no storage with
n; assigning one pointer to the other would instead create reference aliasing. Since the entries are integers, copying the entries also gives the required deep copy of this representation.The pointer argument must be passed by reference, because it is replaced:
procedure Lengthen(var n: number)
old := n
L := len(old)
new(result, 2*L)
for i := 0 to L-1 do
result[i] := old[i]
for i := L to 2*L-1 do
result[i] := 0
n := resultThe low-order coefficients are preserved and the newly allocated high-order coefficients are zero, so the digit-array integer representation has the same value. The allocation remains nonempty because . Neither allocation nor an uninitialized high-order cell may be assumed to contain zero. Any other reference to the old array still denotes that old array; the code does not free storage through an alias.
Propagate each carry into the next position, lengthening the array if necessary:
procedure Normal(var n: number)
i := 0
while i < len(n) do
carry := floor(n[i] / base)
n[i] := n[i] - carry*base
if carry != 0 then
if i+1 = len(n) then
assert carry > 0
Lengthen(n)
n[i+1] := n[i+1] + carry
i := i+1The integer division identity gives a normalized remainder in . The local rewrite preserves value because a carry at position contributes exactly what was removed at position . The loop invariant is that the represented value is fixed and every position below
i is normalized. Under the stated nonnegative-digit assumption all carries are nonnegative. Carries eventually stop beyond the finite radix expansion of the represented integer; scanning any spare allocated zeros then terminates.This implementation also accepts signed temporary coefficients when their total represented value is nonnegative, using floor division rather than truncation toward zero. A negative carry out of the final position would make the entire represented value negative, since the already normalized lower part is smaller than the next radix power. Thus the assertion cannot fail for a nonnegative represented value. This extended carry normalization of a digit array also makes the arithmetic routines below robust to such temporary representations.
function MakeNum(t: integer): number
require t >= 0
new(result, 1)
result[0] := t
Normal(result)
return resultBefore normalization its represented value is exactly
t. Carry normalization of a digit array preserves that value and grows storage when needed. Zero returns a valid nonempty representation containing zero. A negative input is outside this nonnegative-number abstraction.function Add(a, b: number): number
L := max(len(a), len(b))
new(result, L)
for i := 0 to L-1 do
result[i] := 0
if i < len(a) then result[i] := result[i] + a[i]
if i < len(b) then result[i] := result[i] + b[i]
Normal(result)
return resultBy the digit-array integer representation, the raw result has value . Carry normalization of a digit array produces a normalized result, including any final carry. Both input arrays remain unchanged, so the operation also works when
a and b alias each other.Use schoolbook multiplication on the digit coefficients:
function Mul(a, b: number): number
new(result, len(a)+len(b))
for k := 0 to len(result)-1 do
result[k] := 0
for i := 0 to len(a)-1 do
for j := 0 to len(b)-1 do
result[i+j] := result[i+j] + a[i]*b[j]
Normal(result)
return resultThis is discrete convolution of the digit arrays. Expanding the product showsbefore normalization. Normalization preserves the value and establishes the digit bounds. Allocating fresh storage makes input aliasing harmless. The convolution uses coefficient products for input lengths . Intermediate products and sums need sufficiently wide or arbitrary-precision arithmetic; fitting each normalized digit into a small integer does not alone prevent accumulator overflow.
Normalize a copy, skip high-order zero blocks, print the highest block ordinarily, and pad all remaining blocks:
procedure OutNum(n: number)
z := CopyNum(n)
Normal(z)
i := len(z)-1
while i > 0 and z[i] = 0 do
i := i-1
Out.Int(z[i])
i := i-1
while i >= 0 do
place := base div 10
while place > 0 do
digit := (z[i] div place) mod 10
Out.Char(character('0' + digit))
place := place div 10
i := i-1Here
Out.Int writes an ordinary unpadded decimal integer, and character('0' + digit) denotes its decimal digit character. Since for , the inner loop writes exactly characters per lower block. This power-of-ten digit-block formatting retains internal zeros: base- digits print as 12000004, not 1204. An all-zero array prints exactly 0. The caller's original array is preserved.Use three-way array partitioning around a saved pivot value:
procedure Partition(var a; l, r; var m, n)
x := a[Pivot(a,l,r)]
m := l
k := l
n := r
while k < n do
if a[k] < x then
swap(a[k], a[m])
m := m+1
k := k+1
else if a[k] > x then
n := n-1
swap(a[k], a[n])
else
k := k+1Assume a total ordering on the element keys. The loop invariant partitions the original segment intowith and the segment's multiset unchanged. A smaller entry exchanges with the first equality position; the displaced equal entry is accounted for when both indices advance. A greater entry exchanges with the last unclassified position, so
k must stay to inspect the incoming entry. The loop variant decreases by one in every branch.At termination the equality interval is . It is nonempty because the pivot value came from the segment and swaps preserve the bag. The stronger strict outer-region conditions therefore imply the requested overlapping inequalities and . Storing the pivot value avoids following an array position whose contents may move.
Four-region invariant for duplicate-aware array partitioning
. The unclassified interval shrinks at every comparison. On completion, the equal interval remains nonempty and both outer intervals can be discarded or searched by rank. Details.
Keep the target as an absolute, zero-based array index:
function Find(i; var a; l, r): T
require l <= i < r
Partition(a,l,r,m,n)
if i < m then
return Find(i,a,l,m)
else if i >= n then
return Find(i,a,n,r)
else
return a[i]The order statistic belongs to the lower segment, equality interval or upper segment according to the index comparison. In the middle interval its value is the pivot; otherwise Quickselect recurses only into the relevant outer interval. The nonempty equality interval guarantees a strictly shorter retained segment. The procedure sorts neither discarded segment. Since indices remain absolute, the right recursion does not subtract
n from i.function Select(i; var a; N): T
require 1 <= i <= N
return Find(i-1,a,0,N)Thus rank is index . The boundary ranks return the minimum and maximum, and repeated values occupy as many ranks as their multiplicities in the multiset.
For an active segment of length , partitioning takes comparisons. If pivot choice costs at most linear time and always leaves at most an fraction on the searched side, the total is bounded by the geometric series , giving time.
Repeatedly choosing an extreme pivot while searching toward the other end retains lengths , giving worst-case time. The equality interval makes an all-equal input finish in one partition. Independent uniform random pivots give expected linear time for duplicate-aware Quickselect, but this is not a deterministic worst-case guarantee. More expensive pivot selection must be included in the cost rather than hidden inside the partition bound.
Each recursive call is a tail call: nothing remains to be computed after it returns. Replace it by an update of the retained bounds:
function Select(i; var a; N): T
require 1 <= i <= N
target := i-1
l := 0
r := N
while true do
Partition(a,l,r,m,n)
if target < m then
r := m
else if target >= n then
l := n
else
return a[target]The loop invariant retains the target order statistic in with . Each nonreturning iteration strictly decreases , because is nonempty. This proves termination and replaces recursive stack space by auxiliary space, apart from the pivot routine's own storage.
Remember the minimum node while scanning the remaining suffix:
function FindMin(xs: List): List
require xs != nil
best := xs
p := xs.next
while p != nil do
if p.x < best.x then best := p
p := p.next
return bestThe loop invariant says that the processed prefix is nonempty,
best is a node of that prefix, and its key is no greater than any other processed key. The links are unchanged. Advancing p extends the prefix by one; the number of unprocessed nodes decreases. When it reaches nil, best is the minimum of the whole finite singly linked list. Strict comparison retains the first minimum among ties.Treat removal of the first node separately; otherwise find its predecessor:
procedure Remove(x: List; var xs: List)
require x is a node reachable from xs
if xs = x then
xs := x.next
else
p := xs
while p.next != x do
p := p.next
p.next := x.next
x.next := nilIn the search branch the loop invariant says that
p is before x in the original linked list, x is reachable from p.next, and no links have yet changed. The remaining link distance to x decreases at every advance, so membership of x guarantees a predecessor is found. Bypassing it removes exactly that cell, rather than an arbitrary equal-valued cell. Detaching x.next leaves a standalone removed node and preserves the relative order and object identities of all retained nodes.A sentinel node is a permanent header whose key is ignored and whose
next field holds the first data node. Every data node then has a predecessor, including the first, so unlinking always updates a predecessor's next field.function DelMin(hd: List): List
require hd != nil and hd.next != nil
bestPrev := hd
p := hd.next
while p.next != nil do
if p.next.x < bestPrev.next.x then
bestPrev := p
p := p.next
result := bestPrev.next
bestPrev.next := result.next
result.next := nil
return resultThe processed data prefix ends at
p. Its minimum is bestPrev.next, and bestPrev remains that node's actual predecessor. This loop invariant is initialized by the first node and preserved when a strictly smaller next node is found. The unprocessed suffix length is a loop variant. At exit, the final splice removes the first minimum in one uniform case. This is linked-list minimum extraction; it requires at least one data node, rather than treating the dummy header as an element.Repeatedly detach the minimum and append that very node to a separate output chain:
function Sort(xs: List): List
allocate dummy headers remaining and output
remaining.next := xs
output.next := nil
tail := output
while remaining.next != nil do
p := DelMin(remaining)
tail.next := p
tail := p
return output.nextThe loop invariant says that the output and remaining chains contain disjoint subsets of the original data nodes, together containing every original node exactly once. The output is nondecreasing, its final key is no larger than any remaining key, and
tail points to its final node, or to the dummy header when empty. Its outgoing link is nil because DelMin detaches the returned node. Appending the remaining minimum preserves all these properties; the remaining node count decreases by one.At exit the output is the complete sorted bag. This iterative selection sort preserves duplicate occurrences and, with first-minimum tie handling, their original relative order. It uses time and auxiliary nodes. “Increasing” here means nondecreasing when equal keys occur.
function GCD(m,n): integer
a := m
b := n
while b != 0 do
r := a mod b
a := b
b := r
return a
procedure Reduce(var m,n)
require m >= 0 and n > 0
d := GCD(m,n)
m := m div d
n := n div dThe loop invariant is with . The nonnegative loop variant is : when positive, the new remainder is strictly smaller. Thus the final is the positive greatest common divisor. Dividing both numerator and denominator by it preserves the rational number and makes them coprime. The stated proper fraction case is included, but the same code works for every nonnegative numerator, a fact useful in part (d). In particular, zero reduces to .
For , is equivalent to . The largest allowed unit fraction therefore has the smallest such integer denominator:The residual is . From we obtainThus the nonnegative numerator strictly decreases at each nonfinal step, and reduction to lowest terms can only decrease it further. This loop variant proves termination of the greedy Egyptian fraction expansion. The case already has the empty expansion and requires no division by .
Accumulate denominators while reducing the positive residual:
procedure fromRat(m,n; var e)
require 0 <= m < n
e.i := 0
while m > 0 do
q := n div m
if n mod m != 0 then q := q+1
assert e.i < N
e.x[e.i] := q
e.i := e.i+1
m := m*q-n
n := n*q
Reduce(m,n)The quotient-and-remainder calculation implements the ceiling exactly. With original inputs , the loop invariant isAll stored denominators are positive;
e.i counts precisely the initialized entries. Part (b) makes a strictly decreasing nonnegative loop variant. At termination the residual is zero, so the stored Egyptian fraction has the original value. The promised capacity bound justifies the array assertion. Denominators can grow rapidly, so the integer operations require exact sufficiently large storage.procedure toRat(e; var m,n)
require 0 <= e.i <= N and every stored denominator is positive
m := 0
n := 1
j := 0
while j < e.i do
q := e.x[j]
m := m*q+n
n := n*q
Reduce(m,n)
j := j+1The loop invariant is that is the reduced fraction equal to the sum of the first terms, with . The update is exactly , and the greatest common divisor reduction preserves it. The loop variant decreases to zero. The empty sum gives .
An arbitrary stored Egyptian sum can be at least one, so this uses the broader nonnegative-numerator contract of the implementation in part (a), not an unjustified assumption that every intermediate fraction is proper.
procedure OutRat(m,n)
Out.Int(m)
Out.String("/")
Out.Int(n)
procedure OutEgypt(e)
if e.i = 0 then
Out.String("0")
else
for j := 0 to e.i-1 do
if j > 0 then Out.String("+")
Out.String("1/")
Out.Int(e.x[j])Ordinary unpadded decimal output and the greedy Egyptian fraction expansion give
5/7 = 1/2+1/5+1/70 for that input. The final newline is supplied by the caller. Stored duplicate denominators, if present in another valid representation, are printed as separate unit fraction occurrences.The prototype pattern is a creational pattern: a client asks a configured object to clone itself through a common object interface, and concrete prototypes implement the cloning operation. The client can thereby create objects without naming their concrete classes at every creation site.
Use it when the required configuration or concrete type is chosen at runtime, or when reconstructing expensive initial state is less convenient than copying a prepared example. A deep copy may be needed for independently mutable nested data; merely duplicating outer fields can leave reference aliasing. The cloning contract determines what is copied and what may safely be shared.
This is the decorator pattern, a structural pattern.
BasicPlan supplies the initial component. Packages stores another CableTV behind the same interface and delegates to it; Movies and HDChannels add their own price and description. Wrapping one package around another combines the optional responsibilities without constructing a subclass for each possible combination.The decorator pattern participants are:
- Component:
CableTVdeclares the commoncostandpackagesqueries, so clients can use both basic and decorated accounts through one object interface. - Concrete component:
BasicPlansupplies the initial price and package description. - Decorator: the abstract
Packagesclass stores a component reference and forwards its operations, enabling recursive object composition. - Concrete decorators:
MoviesandHDChannelsoverride the queries to add one responsibility while preserving the wrapped component's behavior. - Client: an application chooses the nesting of components and observes the resulting account through
CableTV.
Each wrapper contributes its price exactly once along the chain. The same structural arrangement handles a new optional package without changing the existing component interface.
Add one concrete decorator and a small application:
class Sports(account: CableTV) extends Packages(account) {
override def cost: Double = super.cost + 5.0
override def packages: String = super.packages + ", Sports"
}
object CableTVExample extends App {
val basic: CableTV = new BasicPlan
val movies: CableTV = new Movies(basic)
val hd: CableTV = new HDChannels(movies)
val sports: CableTV = new Sports(hd)
Seq(basic, movies, hd, sports).foreach { account =>
println(account.packages + " = £" + account.cost)
}
}The output is:
Basic plan = £30.0
Basic plan, Movies = £40.0
Basic plan, Movies, HD channels = £47.0
Basic plan, Movies, HD channels, Sports = £52.0The final price is £52. Each new wrapper leaves earlier account objects available at their original prices. In the UML class diagram, both
BasicPlan and Packages realize CableTV; each package class inherits Packages. The account relationship points from the decorator to another CableTV component. It is an association, without asserting exclusive lifetime ownership.
Cable TV decorator classes extended with the Sports package
. Original UML class diagram. Dashed hollow-triangle arrows denote interface realization; solid hollow-triangle arrows denote class inheritance. The account association permits nested decorators. Details.
A sequence diagram shows participants as lifelines and the order of messages between them, usually with time progressing downward. It can show a client asking a sports wrapper for its price, followed by nested calls through the other decorators to the basic component, then replies carrying the accumulated cost.
A state diagram shows the possible states of a system and event-triggered transitions, with optional guards and actions. For an account, it might distinguish active, suspended and closed states and the events allowing a change.
Both are behavioral UML views, but a sequence diagram emphasizes ordered interactions between participants; a state diagram emphasizes states and permitted transitions. A lifecycle state diagram can admit many different message traces.
Keep a buffered first match and a flag recording whether the initial prefix still needs to be skipped:
class DropUntil[T] private (
p: T => Boolean,
iter: Iter[T],
private var cached: Option[T],
private var seeking: Boolean) extends Iter[T] {
def this(p: T => Boolean, iter: Iter[T]) =
this(p, iter, None, true)
private def prepare(): Unit = {
if (seeking) {
while (cached.isEmpty && iter.hasNext) {
val x = iter.next()
if (p(x)) cached = Some(x)
}
seeking = false
}
}
def hasNext: Boolean = {
prepare()
cached.nonEmpty || iter.hasNext
}
def next(): T = {
prepare()
cached match {
case Some(x) => cached = None; x
case None =>
if (!iter.hasNext) throw new NoSuchElementException("DropUntil.next")
iter.next()
}
}
def copy(): Iter[T] = {
prepare()
new DropUntil[T](p, iter.copy(), cached, false)
}
}While seeking,
prepare drops exactly the rejected prefix and caches the first accepted value, including a possible null payload as Some(null). Afterwards the abstract remainder is the cache, if any, followed by the underlying remainder; later values are returned even when they fail p. Repeated hasNext calls do not lose the cached value.The iterator snapshot copies the underlying cursor and the cached value, then marks the initial search complete. It does not reconstruct a fresh two-argument
DropUntil, which could incorrectly discard later values. Resolving the initial search before copying also avoids having two snapshots independently rerun a privately stateful predicate. The wrapper owns consumption of the supplied source cursor. If that source is infinite and never produces an accepted value, seeking cannot finish. This is a prefix-dropping iterator, rather than a repeatedly demand-driven filtering iterator.These methods consume the receiver's remaining sequence;
exists stops as soon as it finds a witness:trait RichIter[T] extends Iter[T] {
def foreach(f: T => Unit): Unit = {
while (hasNext) f(next())
}
def exists(p: T => Boolean): Boolean = {
while (hasNext) {
if (p(next())) return true
}
false
}
def foldLeft[U](x: U)(f: (U,T) => U): U = {
var result = x
while (hasNext) result = f(result, next())
result
}
}After consumed elements,
foreach has invoked its callback on exactly that prefix, exists has found no witness in it unless it has already returned, and the left fold accumulator is the fold of that prefix in its original order. These loop invariants prove the finite-sequence results. On an infinite sequence, exists may still terminate when it reaches a witness; a full traversal or fold generally does not. To retain the original cursor, a caller can invoke the operation on a suitable copy.import scala.collection.immutable.Stream
class FunIter[T] private (
private var rest: Stream[T]) extends Iter[T] {
def this(v: T, f: T => T) = this(Stream.iterate(v)(f))
def hasNext: Boolean = true
def next(): T = {
val result = rest.head
rest = rest.tail
result
}
def copy(): Iter[T] = new FunIter[T](rest)
}For a total step function, the stream is infinite and its values are . At every call,
rest starts with the next unconsumed value. Copying that reference gives a new cursor at exactly the same position; later cursor assignments are independent.The memoized iterator snapshot is useful for the next part: if
f owns private mutable state, advancing either cursor realizes a previously unknown tail only once, and both copies can then read the same cached values. Merely constructing new FunIter(current, f) would share the mutable closure while generating two independent futures, which could diverge. Memoization instead makes the generated sequence shared and the consumption positions independent. The closure must not be mutated externally, and generic element payloads are shared rather than deep-copied. Retaining an old cursor can retain cached cells.[ref]Scala 2.12 Stream API documentation. Opening memoization example and notes on retained heads
Give the step function one private previous-value cell, freshly allocated for each independent Fibonacci generator:
def fibonacci(): Iter[BigInt] = {
var previous = BigInt(1)
val step: BigInt => BigInt = { current =>
val following = previous + current
previous = current
following
}
new FunIter[BigInt](BigInt(0), step)
}The initial artificial previous value is , making the first update return one. Thereafter, just before advancing from , the captured cell holds ; the assignment produces and retains . Induction gives .
BigInt avoids the fixed-width overflow that would prevent Int from representing all Fibonacci numbers.Copies made through part (c) share memoized future cells, so interleaving their traversal does not advance this private state twice for the same sequence position. A separate call to
fibonacci() receives a separate closure. Another valid construction uses a pure step on the pair and projects the first coordinate; the stateful construction above follows the suggested single-current-value approach.The three printed lines are:
g in A, f in C
h in B, f in A
k in A, h in B, f in AThe inherited
A.g makes an ordinary virtual call to f, selecting C.f by dynamic dispatch. B.h instead invokes super.f, which selects the next implementation after B, namely A.f. Finally, A.k makes an ordinary virtual call to h, selecting B.h and its already determined result. A super call is not redirected back to the most-derived override.Ignoring the predefined universal bases, the Scala trait linearizations are
D1, B2, B1, A and D2, B1, B2, A. The rightmost mixed-in trait is searched first, while the shared base occurs only once.The output is:
h in B2, g in B1, f in A
h in B1, g in B2, f in AFor
D1, h is the B2 implementation. Its super.g continues after B2 to B1.g; that method's super.f continues after B1 to A.f. The second line follows the reversed mixin order. In particular, a trait's unqualified super is interpreted in the concrete receiver's linearization, not by assuming the trait always sees only its textual parent.[ref]The printed lines are:
f with X at M
f with Y at N
f with Y at NMethod overloading first uses static types. The receiver
m has static type M, whose available signatures are f(X) and f(Y). Argument x selects f(X); y selects f(Y); and z, statically Z, also selects f(Y) because that is the most specific available applicable signature. N.f(Z) is not available through the static receiver type.Only after a signature is selected does dynamic dispatch choose an override for the runtime receiver
N. That class overrides f(Y) but not f(X), explaining all three lines. The shared argument object's runtime class does not trigger a second overload-resolution pass.Replace the overloaded entry family by one forwarding method and introduce the second dispatch explicitly:
class X {
def dispatch(to: M): String = to.visit(this)
}
class Y extends X {
override def dispatch(to: M): String = to.visit(this)
}
class Z extends Y {
override def dispatch(to: M): String = to.visit(this)
}
class M {
def f(x: X): String = x.dispatch(this)
def visit(x: X): String = "f with X at M"
def visit(x: Y): String = "f with Y at M"
def visit(x: Z): String = "f with Z at M"
}
class N extends M {
override def visit(x: X): String = "f with X at N"
override def visit(x: Y): String = "f with Y at N"
override def visit(x: Z): String = "f with Z at N"
}The original three calls still type-check because all their arguments are subtypes of
X. They all refer to the same runtime Z object already; the change is how the operation discovers that runtime type. The first virtual call selects Z.dispatch, where this has static type Z, so overload resolution selects visit(Z). The second virtual call selects N.visit(Z) from the receiver's runtime type. Thus double dispatch gives f with Z at N on all three lines.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.