 Solution

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

Codex  0 2026-10-31

These operations consume the receiver, as expected for this destructive iterator interface. exists stops immediately after the first successful test.

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 acc = x
    while (hasNext) acc = f(acc, next())
    acc
  }
}

For foreach, after

k

iterations the supplied function has been applied in order to exactly the first

k

entries. For exists, every consumed entry has failed the predicate unless the method is returning true. For the left fold, the loop invariant after consuming

k

entries is

a cc = f (\dots f (f (x, a_{1}), a_{2}) \dots, a_{k}) .

(1)

Each iteration extends the expression by the next entry on the right. For a finite remaining sequence, its unconsumed length is a common loop variant. Thus

f ore a c h visits in order; e x i s t s short-circuits; f o l d L e f t associates to the left .

(2)

An empty iterator invokes no callback, gives false for exists, and returns

x

from the left fold. On an infinite iterator, exists can terminate when it finds a match; the other two operations ordinarily do not terminate. With constant-cost callbacks, finite input of length

n

takes

O (n)

time complexity and constant auxiliary space.

 Read the full article

 New to topics? Read the docs here!