Worked solutions for the held Oxford Long Vacation examination of 6 September 2022. Source release: released examination PDF. The cover date controls the identity despite the archive's older directory name. All eight questions and all 44 marked leaves are addressed, including alternatives not required of one candidate. No question statements or source figures are reproduced.
Code uses Scala 2 syntax. Mathematical invariants distinguish exact arithmetic from floating-point execution, and fixed-width sizes and counts are checked where necessary. Mutable structures are assumed to be used sequentially, with their stated representation invariants; destructive iterator adapters own their input states exclusively. Each question has its own code context, so the sparse-vector
Node and tree Node[T] are independent definitions. No source attachment is missing.Imperative Programming Part 1.
Use a
Double base so that the reciprocal is not truncated by integer division. Repeated multiplication gives the requested linear-work approximation to Euler's number.def eaLinear(n: Int): Double = {
require(n > 0)
val base = 1.0 + 1.0 / n.toDouble
var i = 0
var result = 1.0
while (i < n) {
result *= base
i += 1
}
result
}In exact arithmetic over the real numbers, the loop invariant is and . It holds initially, one multiplication establishes the next exponent, and at exit gives the specified power. The nonnegative loop variant is . There are exactly loop multiplications, hence in asymptotic analysis, and one division to form the base. With floating-point arithmetic, the invariant describes the intended exact result; the actual output has the corresponding rounding errors.
def eaFast(n: Int): Double = {
require(n > 0)
var remaining = n
var base = 1.0 + 1.0 / n.toDouble
var result = 1.0
while (remaining > 0) {
if (remaining % 2 == 1) result *= base
base *= base
remaining /= 2
}
result
}Writing , the exact-arithmetic loop invariant is and . For an even integer exponent , replace the base by its square and the exponent by . For an odd integer exponent , first multiply the accumulator by the base and then make the same replacement. Both preserve the product. The loop variant is
remaining, which strictly decreases while positive. At exit the remaining exponent is zero, so the returned value approximates .There are iterations, squarings and one accumulator multiplication for each set bit of : between and multiplications. Thus the bound is as , or including the small case . All power variables are
Double; no unintended Int squaring occurs.Maintain the reciprocal factorial term rather than calculating large factorials separately:
def eb(n: Int): Double = {
require(n > 0)
var i = 0
var term = 1.0
var sum = 1.0
while (i < n) {
i += 1
term /= i.toDouble
sum += term
}
sum
}The exact-arithmetic loop invariant is , , and . It holds for because . Dividing by the new index produces the next reciprocal factorial; adding it extends the partial sum. The loop variant is . At exit the sum includes all terms from through , using exactly divisions and no multiplications in the loop. In particular, the initial
1.0 accounts for the zero-index term. The work bound is , with constant auxiliary space.Avoid forming the enormous powers in the original ratios. Put , and ; algebra givesUse simultaneous exponentiation by squaring to compute the two powers with one loop and a shared remaining exponent:
def ec(n: Int): Double = {
require(n > 1)
val dn = n.toDouble
val a = 1.0 + 1.0 / dn
val b = 1.0 + 1.0 / (dn - 1.0)
var remaining = n - 1
var u = a
var v = b
var pa = 1.0
var pb = 1.0
while (remaining > 0) {
if (remaining % 2 == 1) {
pa *= u
pb *= v
}
u *= u
v *= v
remaining /= 2
}
((dn + 1.0) * a) * pa - dn * pb
}The exact-arithmetic loop invariant is , and . The even integer and odd integer cases preserve both equalities in parallel. The loop variant is
remaining. On termination, the displayed expression is exactly the desired approximation in the ideal arithmetic model. For , the loop uses at most multiplications, followed by three more: multiplications and one loop.Converting
n to Double before adding one also avoids overflowing n + 1 at Int.MaxValue. The algebra avoids power overflow but does not remove catastrophic cancellation: the final subtraction combines quantities of order to obtain a result of order . For sufficiently large , floating-point rounding can outweigh the mathematical truncation error. For example, at n == 1000000 this Double computation returns approximately 2.7180521293, although the exact formula is approximately 2.71828182845916. Arbitrarily many requested decimal digits require increased arithmetic precision, not simply a larger Int argument.Use the reciprocal-factorial sum for increasing accuracy. Let be the requested number of decimal places and use absolute error tolerance proportional to . Expanding gives and , so these are genuine first nonzero error orders. The first approximation needs of order . Even its fast implementation therefore uses multiplications, while the linear version uses exponentially many in . The third approximation needs of order , but its fast powering still uses multiplications, with two parallel accumulators and a cancellation-prone subtraction.
For the Taylor series sum, Stirling's formula gives , so a sufficient term count grows as . Its divisions therefore grow more slowly than the multiplication counts of either fast-power alternative. More concretely, its positive tail satisfiesThe first omitted term also gives a lower bound . This is the reciprocal-factorial series remainder bound, supplying an explicit stopping certificate rather than relying only on Big O notation. It follows by bounding every successive tail denominator factor below by .
The sum also avoids subtraction of nearly equal large values and has small positive terms, making it numerically preferable. For a particular small accuracy request, constants and actual term counts may be compared directly; an asymptotic error bound alone does not prove a universal finite-input operation ranking. With ordinary
Double, sufficiently many tiny positive terms stop changing the rounded sum, so beyond machine precision a higher-precision version is necessary regardless of the formula.
Arithmetic work for eight decimal-accuracy targets, using high-precision reference errors rather than Double error estimates
. Details. 
def search(f: Array[Array[Int]], x: Int): Option[(Int, Int)]Some((i,j)) denotes a match; None denotes absence. The extra array argument makes the dependence on the searched data explicit; if f is already enclosed in the surrounding scope, it can instead be omitted. For all implementations below, assume f is non-null, its rows are non-null and rectangular, and it remains unchanged during the search. Empty dimensions are permitted.def searchUnordered(f: Array[Array[Int]], x: Int): Option[(Int, Int)] = {
val n = f.length
val m = if (n == 0) 0 else f(0).length
var i = 0
while (i < n) {
var j = 0
while (j < m) {
if (f(i)(j) == x) return Some((i, j))
j += 1
}
i += 1
}
None
}The outer loop invariant excludes every entry in earlier rows; the inner one also excludes columns before
j in the current row. Failed equality tests preserve these exclusions. The inner and outer loop variants are and , respectively. A successful return identifies an actual match, while exhaustion excludes the entire array. At most entries are inspected.The source's “at least ” should be read as a worst-case lower bound, using the correct asymptotic direction. If any entry were left unread on an all-nonmatching input, changing only that entry to would leave the observations identical while changing the answer. Thus every always-correct procedure needs inspections in the worst case, and this algorithm achieves entry inspections. Empty dimensions return absence; the asymptotic claim concerns nonempty arrays.
Use a lower-bound search separately in each nondecreasing row:
def searchRows(f: Array[Array[Int]], x: Int): Option[(Int, Int)] = {
val n = f.length
val m = if (n == 0) 0 else f(0).length
if (m == 0) return None
var i = 0
while (i < n) {
var lo = 0
var hi = m
while (lo < hi) {
val mid = lo + (hi - lo) / 2
if (f(i)(mid) < x) lo = mid + 1
else hi = mid
}
if (lo < m && f(i)(lo) == x) return Some((i, lo))
i += 1
}
None
}The outer loop invariant says there is no match in earlier rows. The inner invariant is , with every value before
lo smaller than and every value from hi onward at least . Sortedness justifies each exclusion, and hi - lo strictly decreases. At exit, a match in this row exists exactly when the lower-bound index is inside the row and holds . Failure extends the outer exclusion.The cost is , conventionally written for ; the extra one matters when a row has a single entry. Storage is constant. The source's column ranges must use indices strictly below , since
f(i)(m) is outside the array.Assume both dimensions are positive so the top-right entry exists. If
f(0)(m-1) == x, it is already a match. If it is smaller than , the entire first row is smaller, since it is that row's maximum; discard the first row. If it is larger than , the entire last column is larger, since it is that column's minimum; discard the last column. This is the staircase matrix search elimination step. Row and column monotonicity are both needed for the respective conclusions.def searchMonotone(f: Array[Array[Int]], x: Int): Option[(Int, Int)] = {
val n = f.length
val m = if (n == 0) 0 else f(0).length
var i = 0
var j = m - 1
while (i < n && j >= 0) {
val v = f(i)(j)
if (v == x) return Some((i, j))
else if (v < x) i += 1
else j -= 1
}
None
}The loop invariant is that any match must lie in rows and columns . Smaller corner values exclude the current row, larger ones exclude the current column, as shown in part (d). The loop variant is nonnegative while the rectangle is nonempty and decreases by one on every unsuccessful inspection. When the loop exits, the rectangle is empty, so absence is established.
At most entries are inspected when both dimensions are positive, giving running time and auxiliary space. An empty dimension causes no entry access. Duplicates do not affect the argument, since every exclusion uses a strict inequality relative to the target.
Imperative Programming Part 2.
The abstract FIFO queue state is a finite sequence , initially empty. Because the interface returns
Int length, use the representable-size model . Its operations are:trait Queue[A] {
// State q: finite sequence of A; initially [].
// Pre: length(q) < Int.MaxValue. Post: q = q0 ++ [x].
def enqueue(x: A): Unit
// Pre: q is nonempty. Post: return head(q0); q = tail(q0).
def dequeue(): A
// Post: q = [].
def clear(): Unit
// Post: q unchanged; return q.isEmpty.
def isEmpty: Boolean
// Post: q unchanged; return length(q).
def length: Int
}The unchanged-state clauses on the two queries are part of their postconditions.
dequeue removes exactly the oldest remaining element, while clear discards all entries regardless of the old state. The size bound can be omitted in an unbounded mathematical model, but it must be reconciled with fixed-width lengths in an implementation.final class QueueNode(val value: Int, var next: QueueNode)A null successor terminates the chain. The stored value need not be mutable for a FIFO queue, because enqueue creates a node and dequeue removes one rather than changing its payload.
private var first: QueueNode = null
private var last: QueueNode = null
private var size = 0The representation invariant requires and a finite acyclic null-terminated linked list of exactly
size nodes starting at first. When size == 0, both endpoints are null. Otherwise last is precisely the final reachable node and last.next == null.The abstraction function maps the chain from first to last to its payload sequence. Initially all pointers are null and the cached size is zero, giving the empty abstract queue. A tail pointer makes append constant-time; the cached size makes the
length query constant-time without traversing the chain.Use the trait and node definition above. The reference to a “stack” in this part is a wording error: the declared class and operations implement a FIFO queue.
class ListQueue extends Queue[Int] {
private var first: QueueNode = null
private var last: QueueNode = null
private var size = 0
def enqueue(x: Int): Unit = {
require(size < Int.MaxValue, "queue size limit")
val fresh = new QueueNode(x, null)
if (last == null) first = fresh
else last.next = fresh
last = fresh
size += 1
}
def dequeue(): Int = {
require(first != null, "empty queue")
val answer = first.value
first = first.next
size -= 1
if (first == null) last = null
answer
}
def clear(): Unit = {
first = null
last = null
size = 0
}
def isEmpty: Boolean = size == 0
def length: Int = size
}Appending links the fresh node after the old tail, or establishes both endpoints when empty. Removing the head preserves the tail unless the final node was removed, in which case both endpoints become null. Clearing only discards the endpoint references; it need not visit or overwrite unreachable nodes. Thus all operations are in the usual pointer-operation/allocation cost model, with later garbage collection excluded from an individual operation's bound. The representation invariant and abstraction function show the specified sequence changes, including empty/singleton transitions.
A list header is a permanent dummy node that represents the list boundary rather than a data entry. A circular linked list links the last node back to the first or to the header. A singly linked list stores only a successor; a doubly linked list stores both successor and predecessor references.
A header provides a stable object even for an empty list, makes insertions and deletions at the ends resemble interior operations, and can hold metadata such as the vector length in this question. In a circular header-based representation, the empty list is the header linked to itself.
A doubly linked list permits backward traversal and constant-time unlinking of a known node without searching for its predecessor. It uses an extra reference per node and requires more pointer updates and a stronger consistency invariant. Finding a node by an arbitrary index can still require a linear scan: bidirectional links alone do not provide random access.
Within the sparse-vector implementation, use:
class Node(var value: Double, val index: Int,
var prev: Node, var next: Node)The header's
index is the fixed vector dimension, so it need not change after construction. For a data node it is the coordinate index. The representation invariant requires a finite simple cycle through the header, reciprocal predecessor/successor links, strictly increasing indices in the forward data-node traversal, indices in , and a nonzero value at every data node. The header's value is ignored. The abstraction function assigns stored values to their indices and zero to all missing coordinates.The numerical code below takes entries to be finite
Double values. Excluding NaN and infinities makes the relationship to a real sparse vector explicit; arithmetic results still follow ordinary floating-point arithmetic.A single header with
index == n, and with both next and prev pointing to itself, represents the entirely zero vector. It has no data nodes. The ignored header value can be 0.0. The vector dimension remains , even though the number of stored nonzero entries is zero.def makeZeroVector(size: Int): Node = {
require(size >= 0, "negative vector length")
val head = new Node(0.0, size, null, null)
head.prev = head
head.next = head
head
}This establishes the circular-link representation invariant in time and uses one header regardless of the number of implicit zeros. For the nonzero dimension mentioned in part (b), simply use
size > 0 at that call site.Assume
vector is a well-formed header satisfying the sparse-vector representation invariant; checking that whole invariant on each operation would require traversing the list. Check the requested bounds and value, then find the first stored coordinate at or after the target.def setElement(vector: Node, value: Double, index: Int): Unit = {
require(vector != null)
require(0 <= index && index < vector.index)
require(value != 0.0 && !value.isNaN && !value.isInfinity)
var p = vector.next
while ((p ne vector) && p.index < index) p = p.next
if ((p ne vector) && p.index == index) p.value = value
else {
val fresh = new Node(value, index, p.prev, p)
p.prev.next = fresh
p.prev = fresh
}
}The scan excludes all smaller stored indices. An existing coordinate is updated without duplicating it; otherwise the new node is spliced immediately before
p, with both directions repaired. The header also serves as the insertion boundary after the final data node. Strict index order and nonzero storage are preserved. The cost is search and pointer work, where is the number of stored entries.An absent coordinate already has value zero. If found, unlink its node in both directions:
def zeroElement(vector: Node, index: Int): Unit = {
require(vector != null)
require(0 <= index && index < vector.index)
var p = vector.next
while ((p ne vector) && p.index < index) p = p.next
if ((p ne vector) && p.index == index) {
p.prev.next = p.next
p.next.prev = p.prev
}
}Identity comparison with the header prevents treating its dimension field as a data index. The splice preserves reciprocal links even when removing the only data node: the two header links then point to the header again. All other coordinates are unchanged, and an absent coordinate causes no mutation. The running time is , with constant work after the node is located.
Append nonzero entries in increasing index order; repeatedly calling
setElement would unnecessarily rescan earlier entries and could make construction quadratic.def makeVector(elems: Array[Double]): Node = {
require(elems != null)
val head = makeZeroVector(elems.length)
var tail = head
var i = 0
while (i < elems.length) {
val v = elems(i)
require(!v.isNaN && !v.isInfinity)
if (v != 0.0) {
val fresh = new Node(v, i, tail, head)
tail.next = fresh
head.prev = fresh
tail = fresh
}
i += 1
}
head
}The loop invariant says that the list represents exactly the nonzero entries of the processed input prefix, in their original coordinate order, and
tail is the final node or the header when none exist. Every append preserves the cycle and ordering. At exit, all input coordinates have their intended values. Construction takes time and data nodes, where is the array length and the number of nonzeros, plus one header. The input array is unchanged.Use sparse dot product by merging indices: only equal coordinate indices can contribute, so merge the two increasing index streams:
def dotProduct(vec1: Node, vec2: Node): Double = {
require(vec1 != null && vec2 != null)
require(vec1.index == vec2.index, "dimension mismatch")
var p = vec1.next
var q = vec2.next
var answer = 0.0
while ((p ne vec1) && (q ne vec2)) {
if (p.index < q.index) p = p.next
else if (q.index < p.index) q = q.next
else {
answer += p.value * q.value
p = p.next
q = q.next
}
}
answer
}The loop invariant states that the accumulator contains all common-coordinate products already passed, while no unprocessed smaller coordinate can acquire a future partner. If one current index is smaller, the other list has no remaining entry at that index, so its product is zero. Equal indices add their product and advance both. Once either list ends, all remaining coordinates of the other have zero partners.
Thus the code computes the dot product in coordinate order, subject to floating-point rounding, using time and constant auxiliary storage. It does not scan implicit zeros or alter either vector, and it also handles both arguments referring to the same header.
A flattened Boolean array stores the whole board in entries, with cell at position
y*N + x. For the pictured board, its bottom-to-top rows are 111111 | 111100 | 111100 | 110000 | 000000 | 000000.A column-height array uses only entries: column contains exactly the cells below height . The pictured board is , with 16 occupied cells. The alternatives are essentially different because the first stores every cell and the second encodes the boundary of an order ideal.
For the flattened Boolean array, the abstraction function selects the true cells. A suitable representation invariant requires the occupied cells to form a order ideal: an occupied implies occupancy of every with . Deleting a northeast rectangle preserves that property.
For column heights, the invariant is , and the abstraction function is . A legal move replaces every for by , preserving the invariant. This is an order-ideal board representation.
For a fair comparison, allow either representation a scalar cached token count:
Count and Legal then take in both. Without that cache, counting needs Boolean inspections versus height additions. A move takes in the worst case in the flattened representation and with heights. Displaying the full square takes character positions in either. Heights use array entries rather than , so they are superior for the requested operations; their initialization also takes only time.class Chomps(N: Int) {
require(N > 0 && N.toLong * N.toLong <= Int.MaxValue)
private val height = Array.fill(N)(N)
private var remaining = (N.toLong * N.toLong).toInt
def Count(): Int = remaining
def Legal(x: Int, y: Int): Boolean =
0 <= x && x < N && 0 <= y && y < height(x)
def Move(x: Int, y: Int): Unit = {
require(Legal(x, y), "illegal move")
var i = x
while (i < N && height(i) > y) {
remaining -= height(i) - y
height(i) = y
i += 1
}
}
def Display(): Unit = {
require(N < 10, "single-digit display labels required")
var y = N - 1
while (y >= 0) {
print(y + " ")
var x = 0
while (x < N) {
print(if (y < height(x)) "* " else " ")
x += 1
}
println()
y -= 1
}
print(" ")
var x = 0
while (x < N) { print(x + " "); x += 1 }
println()
}
}The strengthened representation invariant includes . The move loop's processed columns have their final truncated heights, unprocessed columns retain their old heights, and each subtraction removes exactly the corresponding height reduction. Because heights are nonincreasing, once a column is no higher than
y, neither is any later column; stopping there is valid. A legal move removes at least one token and leaves a order ideal.The constructor computes in
Long and checks representability before converting, avoiding integer overflow in the cached Int count. Legal rejects out-of-range coordinates before indexing. The methods meet the bounds in part (a); Display additionally checks its stated single-digit-label assumption.Retry invalid inputs without switching players; after a legal move, check whether the board has become empty:
val game = new Chomps(6)
var player = 1
while (game.Count() > 0) {
game.Display()
var accepted = false
var x = 0
var y = 0
while (!accepted) {
try {
println("Player " + player + ": enter x, then y")
x = scala.io.StdIn.readInt()
y = scala.io.StdIn.readInt()
accepted = game.Legal(x, y)
if (!accepted) println("That cell is not a legal move; try again.")
} catch {
case _: NumberFormatException => println("Please enter integer coordinates.")
}
}
game.Move(x, y)
if (game.Count() == 0)
println("Player " + player + " loses; player " + (3 - player) + " wins.")
else player = 3 - player
}Only a move at can remove the poisoned bottom-left token, and that move removes the entire remaining order ideal, so the empty-board test identifies the losing player correctly. Any other legal move preserves that token. Every accepted move strictly decreases the finite token count, giving at most 36 accepted moves. Invalid attempts do not change the board or the turn. As usual for this interactive fragment, the user is assumed eventually to supply another readable input rather than permanently ending the input stream or retrying forever.
Imperative Programming Part 3.
The missing preconditions are for insertion and for deletion and indexing. The inclusive endpoint permits appending; deletion or access at the length is invalid. Specify the initial state, for example , as well as the read-only frame conditions: indexing returns the indicated character and preserves , while
length returns and preserves .The insertion and deletion clauses already describe the new sequence, but their returned values and effects should be interpreted against the old state. For a machine-sized length, insertion also requires . These clauses complete the document abstract data type without prescribing one storage representation.
class DocImp extends Doc {
private val data = scala.collection.mutable.ArrayBuffer.empty[Char]
def insert(pos: Int, ch: Char): Unit = {
require(0 <= pos && pos <= data.length)
require(data.length < Int.MaxValue)
data.insert(pos, ch)
}
def delete(pos: Int): Char = {
require(0 <= pos && pos < data.length)
data.remove(pos)
}
def apply(pos: Int): Char = {
require(0 <= pos && pos < data.length)
data(pos)
}
def length: Int = data.length
}The representation invariant is that
data is a well-formed private dynamic array of at most Int.MaxValue characters. Its abstraction function is the buffer's character sequence. Initialization is empty; insertion and removal at the checked position implement exactly the required sequence edits, and the queries do not modify it.length and indexing are because a dynamic array stores its used length and supports address arithmetic for indexed access. An insertion or deletion at position in a document of length shifts entries; insertion can additionally resize the backing storage, giving amortized time and worst-case for one operation. Deletion is with an additional constant term.Building a document by appending the characters of a length- string costs amortized time, since geometric capacity growth copies a total of only entries. Thus this implementation does not have the quadratic append behavior of repeated immutable-string concatenation. A known final length can also be reserved in advance. The bounds use the usual amortized analysis of a dynamic array.[ref]
Performance Characteristics of Scala 2.13 collections. Mutable sequence table: ArrayBuffer constant indexed access and amortized constant append
Use a fixed-size count array and protected hooks defining a stable character-to-slot mapping. The default hooks count the ASCII lowercase interval. The document must start empty, and all subsequent edits must pass through the mixin methods, as they do for
new DocImp with CharCountPlugin.trait CharCountPlugin extends Doc {
protected def firstCounted: Char = 'a'
protected def numberCounted: Int = 26
protected def slot(ch: Char): Int = {
val k = ch.toInt - firstCounted.toInt
if (0 <= k && k < numberCounted) k else -1
}
private lazy val totals = Array.fill(numberCounted)(0)
abstract override def insert(pos: Int, ch: Char): Unit = {
val k = slot(ch)
super.insert(pos, ch)
if (k >= 0) totals(k) += 1
}
abstract override def delete(pos: Int): Char = {
val removed = super.delete(pos)
val k = slot(removed)
if (k >= 0) totals(k) -= 1
removed
}
def count(ch: Char): Int = {
val k = slot(ch)
require(k >= 0, "character is outside the counted alphabet")
totals(k)
}
}The additional representation invariant is that each array slot equals the number of corresponding characters in the current document. Initially all counts are zero. Each successful underlying edit changes exactly one relevant count, while a failed position check throws before any count is changed. Returning the actual deleted character lets deletion adjust the correct slot.
count takes time for the fixed alphabet, as do the mixin's additions to edit cost. The lazy array avoids reading subclass-overridden size hooks during trait construction; the hooks must remain stable. An extension can override the interval hooks, or override slot with another fixed finite mapping. This is stackable modification by a trait: abstract override permits the method to call the next implementation of super, supplied here by DocImp.[ref]Reuse the machinery with the digit interval:
trait DigitCountPlugIn extends CharCountPlugin {
override protected def firstCounted: Char = '0'
override protected def numberCounted: Int = 10
}Its
count precondition is now '0' <= ch && ch <= '9'. It counts digits while permitting all characters to be stored. This is an alternative configured counter, rather than a second independent lowercase counter in the same object; simultaneous independent alphabets would require separate counters or a combined mapping.Construct the mixed object with a concrete document implementation beneath the plugin:
val doc: DocImp with CharCountPlugin = new DocImp with CharCountPluginIts type combines
DocImp and CharCountPlugin, so document operations and count are available. For example, inserting two 'a' characters and then deleting one leaves doc.count('a') == 1. The plugin is on the right of the concrete superclass in Scala's composition, so its edit methods extend the underlying implementations.Cache only a requested current element. Merely constructing the cursor, or asking whether it is nonempty, must not fetch a value from the iterator:
def asCursor[T](it: Iter[T]): Cursor[T] = new Cursor[T] {
private var cached: Option[T] = None
def hasCurrent: Boolean = cached.nonEmpty || it.hasNext
def current: T = {
if (cached.isEmpty) {
require(it.hasNext, "empty cursor")
cached = Some(it.next())
}
cached.get
}
def next(): Unit = {
if (cached.nonEmpty) cached = None
else {
require(it.hasNext, "empty cursor")
it.next()
()
}
}
}The abstraction function for the adapter is
it.seq when no value is cached and [cachedValue] ++ it.seq otherwise. Fetching current removes one underlying iterator value but saves it, so the cursor's abstract sequence is unchanged; repeated reads return the same value. Advancing either discards that cache or consumes one uncached iterator value. No following element is prefetched.A too-eager implementation could call
it.next() at construction, or fetch a new element immediately after every advance, even when the client never requests it. That can trigger unnecessary work or nontermination on a difficult stream. This lazy iterator-to-cursor adapter avoids both behaviors and checks the underlying access preconditions itself. The wrapped iterator is assumed to be used exclusively through the adapter; independent external consumption would invalidate the shared-state abstraction.def asIter[T](cur: Cursor[T]): Iter[T] = new Iter[T] {
def hasNext: Boolean = cur.hasCurrent
def next(): T = {
require(cur.hasCurrent, "empty iterator")
val answer = cur.current
cur.next()
answer
}
}The two abstract sequences are identical. A
next call returns the old head and removes it, while hasNext only queries availability. No element is read at construction or during an availability test, and no later element is read while returning the current one. Thus the adapter is not too eager. The source's Cursor.current clause needs the implicit precondition that its sequence is nonempty; taking the head of an empty sequence is undefined. The checks above satisfy that requirement even without relying on the client convention.Map a pure, terminating function only when a value is demanded; use the adapters to obtain the cursor form with caching:
def map[T, U](f: T => U, it: Iter[T]): Iter[U] = new Iter[U] {
def hasNext: Boolean = it.hasNext
def next(): U = {
require(it.hasNext, "empty iterator")
f(it.next())
}
}
def map[T, U](f: T => U, cur: Cursor[T]): Cursor[U] =
asCursor(map(f, asIter(cur)))Each demanded output is the function applied to the corresponding input, preserving order and lazy access even for an infinite sequence. The cursor adapter caches its mapped current value, so repeated reads need not recompute
f. Totality/purity of f is the usual assumption for the mathematical sequence-map postcondition; an exception-throwing or state-changing function would need additional behavioral clauses.Both functions may be named
map because their second parameter types differ, Iter[T] versus Cursor[T]. Method overloading selects the applicable signature; its distinction is not based solely on the return type.A single flag represents whether the only element remains:
def unitIter[T](t: T): Iter[T] = new Iter[T] {
private var available = true
def hasNext: Boolean = available
def next(): T = {
require(available, "empty iterator")
available = false
t
}
}
def unitCursor[T](t: T): Cursor[T] = new Cursor[T] {
private var available = true
def hasCurrent: Boolean = available
def current: T = {
require(available, "empty cursor")
t
}
def next(): Unit = {
require(available, "empty cursor")
available = false
}
}The abstract sequence is
[t] while the flag is true and empty afterward. current leaves it unchanged; either advance consumes its sole element. Renaming both methods to unit would leave identical parameter signatures differing only in result type, which cannot define two such Scala overloads.def cat[T](t: Iter[T], u: Iter[T]): Iter[T] = new Iter[T] {
def hasNext: Boolean = t.hasNext || u.hasNext
def next(): T = {
if (t.hasNext) t.next()
else {
require(u.hasNext, "empty iterator")
u.next()
}
}
}
def cat[T](t: Cursor[T], u: Cursor[T]): Cursor[T] = new Cursor[T] {
def hasCurrent: Boolean = t.hasCurrent || u.hasCurrent
def current: T = {
if (t.hasCurrent) t.current
else {
require(u.hasCurrent, "empty cursor")
u.current
}
}
def next(): Unit = {
if (t.hasCurrent) t.next()
else {
require(u.hasCurrent, "empty cursor")
u.next()
}
}
}Assume the two destructive inputs have noninterfering states; in particular, passing the same iterator twice does not create a replayable copy of its original sequence. Fresh independent iterators provide that behavior. Under this ownership condition, the abstraction function is always the concatenation
t.seq ++ u.seq. Consumption from t removes the concatenation's head; once t is empty, consumption from u does so. Availability tests short-circuit, so an infinite first sequence never unnecessarily touches the second.For finite lengths , under a client loop with one availability test and one advance per element, the iterator version directly invokes
t.hasNext times, including the final false test. For a cursor client with one availability test, one current read and one advance per element, the corresponding count is . These count calls made by the shown adapters, not extra checks hidden inside arbitrary underlying methods. A client can repeat availability/current queries arbitrarily often, so no bound depending only on applies without such a client protocol.Cache a permanent “first input exhausted” flag after the first negative test to avoid repeated queries to
t while traversing u; this reduces the dependence to first-input queries under the same protocols. Availability caching can reduce additional repeated checks. The flag is sound because an iterator's consumed sequence does not spontaneously grow again.Keep a FIFO queue of pending child iterators, ordered by the breadth-first order of their parents. Defer even the call creating a node's children until that iterator reaches the front and is needed:
def breadthFirst[T](node: Node[T]): Iter[Node[T]] = {
def childrenLater(n: Node[T]): Iter[Node[T]] = new Iter[Node[T]] {
private lazy val children = n.children()
def hasNext: Boolean = children.hasNext
def next(): Node[T] = {
require(children.hasNext, "empty child iterator")
children.next()
}
}
val pending = scala.collection.mutable.Queue.empty[Iter[Node[T]]]
pending.enqueue(childrenLater(node))
new Iter[Node[T]] {
private def normalize(): Unit = {
while (pending.nonEmpty && !pending.head.hasNext) pending.dequeue()
}
def hasNext: Boolean = {
normalize()
pending.nonEmpty
}
def next(): Node[T] = {
normalize()
require(pending.nonEmpty, "no more descendants")
val answer = pending.head.next()
pending.enqueue(childrenLater(answer))
answer
}
}
}Here “descendants” excludes the supplied root: the first output is its first child. A self-inclusive convention can prepend
unitIter(node) without changing the traversal logic. The queue invariant says its iterators enumerate the still-unreported children of already encountered parents, in parent breadth-first order. Consuming one child appends that child's deferred iterator after all earlier parents' pending children. Exhausted child iterators contribute nothing and can be discarded. This proves increasing depth and sibling order without constructing a complete level in advance.This lazy breadth-first traversal with child iterators never eagerly materializes all children or the whole tree. A finite prefix can therefore be traversed on a genuinely infinite tree. As with any strict breadth-first ordering, an infinite earlier level prevents reaching a deeper level; no algorithm can place a deeper node after every member of an infinite earlier level at a finite output position. For a locally finite tree, every finite-depth level is finite and each descendant is eventually reached, assuming the underlying iterator operations terminate. Fresh child iterators and exclusive ownership of consumed iterator states are essential to this argument.
Use the heap-numbered binary tree with root label zero and children . Its strict descendants in breadth-first search order are . A machine-safe
Node[Int] version stops at the largest representable label:class NumberNode(val label: Int) extends Node[Int] {
require(label >= 0)
def children(): Iter[Node[Int]] = new Iter[Node[Int]] {
private var candidate = 2L * label.toLong + 1L
private val last = candidate + 1L
def hasNext: Boolean = candidate <= last && candidate <= Int.MaxValue
def next(): Node[Int] = {
require(hasNext)
val answer = new NumberNode(candidate.toInt)
candidate += 1L
answer
}
}
}
val traversal = breadthFirst(new NumberNode(0))
var expected = 1
while (expected <= 1000) {
assert(traversal.hasNext)
assert(traversal.next().label == expected)
expected += 1
}The arithmetic is widened before computing child labels, so no negative wrapped labels occur. Repeated
hasNext calls should not skip nodes; a leaf root should produce immediate exhaustion, and uneven finite trees should retain sibling order across parents. A fresh second traversal should start again at one.Literal unbounded increase is impossible with the bounded
Int type. For a genuinely infinite test, change the label and child arithmetic to BigInt; the same construction then has no representational endpoint. The shown finite-prefix test already exercises lazy traversal without allocating the entire very large Int-labelled tree.A complete multiset is a finite-support signed count function. An absent key has count zero; negative counts are allowed. One simple default implementation uses a protected immutable association list with unique keys and nonzero values. Its default is empty, and optimized subclasses may override the public queries.
trait CompleteMultiSet[T] {
// Representation contract: finite, immutable, unique keys, nonzero counts.
protected def entries: List[(T, Int)] = Nil
def count(t: T): Int =
entries.find { case (key, _) => key == t }.map(_._2).getOrElse(0)
lazy val present: Seq[T] = entries.map(_._1)
private def combine(other: CompleteMultiSet[T],
op: (Int, Int) => Int): CompleteMultiSet[T] = {
val keys = (present.toList ++ other.present.toList).distinct
val resultRows = keys.flatMap { t =>
val n = op(count(t), other.count(t))
if (n == 0) Nil else List((t, n))
}
new CompleteMultiSet[T] {
override protected val entries: List[(T, Int)] = resultRows
}
}
def +(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
combine(other, (a, b) => java.lang.Math.addExact(a, b))
def -(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
combine(other, (a, b) => java.lang.Math.subtractExact(a, b))
def max(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
combine(other, (a, b) => math.max(a, b))
def min(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
combine(other, (a, b) => math.min(a, b))
def <=(other: CompleteMultiSet[T]): Boolean =
(present.toList ++ other.present.toList).distinct.forall { t =>
count(t) <= other.count(t)
}
override def toString: String =
present.distinct.filter(t => count(t) != 0)
.map(t => s"$t:${count(t)}").mkString("{", ", ", "}")
}The representation invariant and abstraction function assign the association-list value at a stored key and zero elsewhere. Every operation preserves both operands and returns a fresh immutable value. The finite-support pointwise operations principle makes the support union sufficient because every operation sends to zero. It is necessary for signed counts: the empty value is not at most a value having count at one key, although the empty left support alone would give a vacuous true comparison. Likewise, pointwise minimum can retain a negative count appearing only in the other operand.
present == List() represents the all-zero, empty complete multiset. The list-backed default count takes time for a first-entry hit or an empty list, and in the worst case for a missing or final key, assuming constant-cost key equality. The default binary operations can consequently take quadratic time; they are deliberately simple defaults, not optimized implementations. The lazy present avoids an early call to a subclass's representation during initialization.Counts use
Int, so addition and subtraction explicitly throw ArithmeticException when the mathematical result is unrepresentable instead of silently wrapping. Equivalently, their mathematical precondition requires representable result counts. This machine-size restriction is separate from permitting negative counts.With the completed default trait from part (a), the expression is well-typed and creates the empty complete multiset, provided the type
T is in scope. Every member has a concrete default, entries is empty, and every count is zero.With only the originally printed abstract trait, it is not a legal instantiation, because abstract queries and operations remain unimplemented. The distinction is whether part (a)'s supplied defaults are in force, rather than any special treatment of anonymous objects.
Use an immutable hash map for the concrete value, omitting zero-count entries:
class CompleteMultiSetImp[T](initial: Map[T, Int]) extends CompleteMultiSet[T] {
private val table = initial.filter { case (_, n) => n != 0 }
override def count(t: T): Int = table.getOrElse(t, 0)
override lazy val present: Seq[T] = table.keys.toVector
}
def cms[T](ts: T*): CompleteMultiSet[T] =
new CompleteMultiSetImp[T](ts.distinct.map(t => (t, 1)).toMap)The abstraction function is the map with implicit zero outside its keys. Immutable storage makes saved values independent of later operations, and the inherited defaults dispatch through the overridden
count and present. A hash lookup has expected constant cost under ordinary hashing assumptions, with collision-dependent worst cases.Repeated arguments still get count one, because the constructor first removes duplicates. All other elements have count zero, satisfying the intended stronger reading of the constructor specification. Treating
ts as a bag and adding one for every repetition would implement a different operation.Nonnegative count functions form a valid subtype of the immutable value interface, but they are not closed under its exact subtraction. Preserve the inherited result type rather than silently changing the subtraction contract:
trait MultiSet[T] extends CompleteMultiSet[T] {
// Additional invariant: count(t) >= 0 for every t.
// Inherited arithmetic still returns CompleteMultiSet[T].
}
class MultiSetImp[T](initial: Map[T, Int])
extends CompleteMultiSetImp[T](initial) with MultiSet[T] {
require(initial.values.forall(_ >= 0), "negative multiplicity")
}
def ms[T](ts: T*): MultiSet[T] =
new MultiSetImp[T](ts.distinct.map(t => (t, 1)).toMap)The invariant guarantees nonnegative multiplicities in every
MultiSet object, and the factory gives each supplied element exactly one occurrence. Since the objects are immutable, inherited operations cannot invalidate that invariant in the receiver. Their declared result is a complete multiset, which can legitimately contain negative counts; for example, subtracting a positive count from zero produces a signed result.If an ordinary multiset-only difference is desired, introduce a separate operation with count , or an interface whose subtraction explicitly has that contract. Replacing the parent's exact difference by truncated difference under the same signature would violate behavioral subtyping; strengthening its precondition to forbid negative results would also fail to implement the parent's unrestricted mathematical contract. Retaining the complete result type above reuses every correct default without that substitution error.
Articles were limited to the first 100 out of 104 total.
Articles by others on the same topic
There are currently no matching articles.