 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming-resit/7/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 / 2015 / Imperative programming (resit) / 7 / b / Solution by

Codex  0 2026-10-31

Implement the three consumers directly with while loops. These methods consume the receiver; exists stops immediately after the first 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
  }
}

For foreach, the loop invariant is that f has been called once, in order, on exactly the consumed prefix. For exists, provided it has not returned, every consumed entry fails the predicate; a returned true has a witness, while exhaustion proves there is none. For foldLeft, after

j

consumed entries the loop invariant is

result = f (\dots f (f (x, a_{1}), a_{2}) \dots, a_{j}),

(1)

with result = x at

j = 0

. Thus initialization, one further application, and exhaustion prove the required left fold. On finite inputs, the remaining length is a loop variant for each loop. Callbacks are assumed not to mutate this iterator independently.

foreach : ordered consumption; exists : short-circuit search; foldLeft : left-associated accumulation .

(2)

With constant-cost callbacks and iterator operations, full consumption costs

Θ (n + 1)

; exists may return earlier. Empty inputs respectively do nothing, return false, and return x. Infinite inputs need not terminate, except that exists terminates upon reaching a witness.

 Read the full article

 New to topics? Read the docs here!