Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 6

A prefix-dropping iterator must preserve the first satisfying element. Reading it to test the predicate physically consumes it from the source, so keep it in a one-element buffer. Once a match is found, return the entire suffix without testing subsequent elements again.

trait Iter[T] {
  def hasNext: Boolean
  def next(): T
  def copy(): Iter[T]
}

class DropUntil[T](p: T => Boolean, iter: Iter[T]) extends Iter[T] {
  private var seeking = true
  private var saved: Option[T] = None

  private def prepare(): Unit = {
    if (seeking) {
      while (saved.isEmpty && iter.hasNext) {
        val x = iter.next()
        if (p(x)) saved = Some(x)
      }
      seeking = false
    }
  }

  def hasNext: Boolean = {
    prepare()
    saved.nonEmpty || iter.hasNext
  }

  def next(): T = {
    prepare()
    saved match {
      case Some(x) => saved = None; x
      case None =>
        if (!iter.hasNext) throw new NoSuchElementException("next")
        iter.next()
    }
  }

  def copy(): Iter[T] = {
    val result = new DropUntil[T](p, iter.copy())
    result.seeking = seeking
    result.saved = saved
    result
  }
}

Assume the source iterator is owned by the wrapper, its copy meets the stated independent-cursor contract, and

p

is a pure function. Before preparation, the logical remainder is the source remainder with its maximal initial failing prefix removed. After preparation, it is the buffered match followed by the source remainder, or simply the source remainder when the buffer is empty. This describes the abstraction function and proves that repeated hasNext calls neither lose the match nor skip more values.

Copying preserves the phase flag and optional buffered value and independently copies the source iterator. It does not rerun the predicate on an already accepted match. A shallow copy of the wrapper alone would give shared iterator consumption, violating the specification. Therefore

DropUntil returns the suffix starting at the first match, with independent copies .

(1)

When no element satisfies

p

, a finite source yields an empty iterator. Seeking can diverge on an infinite source with no match; this is inherent in determining whether its required suffix begins anywhere. An element object is not deep-copied by this cursor operation.

b

 0  0

Solution

 0  0

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.

c

 0  0

Solution

 0  0

A simple current-value implementation works when

f

is a pure function, but sharing a mutable closure between copies would violate the independence requirement used in part (d). Use a memoized successor chain for stateful iterator copies: the generated sequence has shared cells, and each iterator has its own current-cell pointer.

object FunIter {
  final class Cell[T](val head: T, f: T => T) {
    lazy val tail: Cell[T] = new Cell[T](f(head), f)
  }
}

class FunIter[T](v: T, f: T => T) extends Iter[T] {
  private var cursor = new FunIter.Cell[T](v, f)

  def hasNext: Boolean = true

  def next(): T = {
    val x = cursor.head
    cursor = cursor.tail
    x
  }

  def copy(): Iter[T] = {
    val result = new FunIter[T](cursor.head, f)
    result.cursor = cursor
    result
  }
}

The representation invariant is that cursor points to the next cell to be returned, and each cell's lazy tail is computed at most once. The abstraction function is the infinite sequence of heads starting at that cell. Advancing changes only this iterator's pointer. A copy starts at the same cell, so both observe the same remaining heads even when their calls are interleaved:

n e x t returns v, f (v), f (f (v)), \dots; co p y preserves an independent position .

(1)

For a stateful

f

, the generator state must be privately owned by this shared chain; unrelated external calls to

f

must not change it. As usual, the values and transition must allow successive results to be observed without externally mutating old results. No interface can independently clone the hidden state of an arbitrary externally mutated closure from its function type alone. The chain avoids needing such cloning: a lagging copy reuses the already generated future instead of invoking

f

again.

Each new cell needs one transition and constant bookkeeping, but retained slower copies can keep a long generated prefix alive. This is an intentional space tradeoff that permits the stateful generator in part (d). No output is possible if computing a demanded transition itself fails or diverges.

d

 0  0

Solution

 0  0

Keep the neighboring Fibonacci number in a private closure. Before calling the transition with

x = F_{n}

, let its captured following equal

F_{n + 1}

def fibonacci(): Iter[BigInt] = {
  var following = BigInt(1)
  val step: BigInt => BigInt = (x: BigInt) => {
    val result = following
    following = x + following
    result
  }
  new FunIter[BigInt](BigInt(0), step)
}

The transition returns

F_{n + 1}

and stores

F_{n} + F_{n + 1} = F_{n + 2}

, preserving the paired Fibonacci recurrence. Initialization gives

F_{0} = 0

and

F_{1} = 1

, so

0, 1, 1, 2, 3, 5, 8, 13, 21, \dots .

(1)

Using BigInt allows all Fibonacci numbers rather than a finite prefix before integer overflow. Replacing BigInt by Int gives the source's suggested machine-integer interface with that limitation. With the FunIter implementation from part (c), each transition runs once per generated cell, and copied iterators can advance independently while sharing the privately owned generator. A simpler alternative uses a pure function on pairs,

(a, b) \mapsto (b, a + b)

, and projects the first component; the closure above follows the source's suggested single-value approach directly.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 6

a

Solution

b

Solution

c

Solution

d

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 6

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion