Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 6 / c / Solution 2026-10-31
View more
A simple current-value implementation works when 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:
(1)
For a stateful , the generator state must be privately owned by this shared chain; unrelated external calls to 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 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.
Read the full article