= Solution
If `f` is a <pure function> on immutable values, a simple implementation stores the next value and copies it into a fresh `FunIter`. Part (d)'s suggested mutable <programming closure>, however, would be shared by such copies and violate independence. A <memoized iterator snapshot> avoids that contradiction: all cursors share already determined <sequence> values, but each has its own position.
``
class FunIter[T](v: T, f: T => T) extends Iter[T] {
private class Cell(val head: T) {
lazy val tail: Cell = new Cell(f(head))
}
private class Cursor(private var cell: Cell) extends Iter[T] {
def hasNext: Boolean = true
def next(): T = {
val answer = cell.head
cell = cell.tail
answer
}
def copy(): Iter[T] = new Cursor(cell)
}
private val cursor = new Cursor(new Cell(v))
def hasNext: Boolean = true
def next(): T = cursor.next()
def copy(): Iter[T] = cursor.copy()
}
``
The first cell stores $v$; its lazily memoized successor stores $f(v)$; the next stores $f(f(v))$, and so on. A cell's successor is evaluated at most once. The <representation invariant> is that each cursor points to the cell holding its next result. `next` returns that result and advances only this cursor. `copy` shares the cell, whose future is memoized, rather than the mutable cursor. Advancing either copy therefore cannot skip entries in the other.
$$
\boxed{\operatorname{next}_j=f^{\,j}(v),\quad j=0,1,2,\ldots;\qquad\operatorname{hasNext}=\texttt{true}.}
$$
Assume each demanded application of `f` terminates and generated values are immutable for purposes of observation. A stateful generator should be privately owned by this family of cursors; arbitrary external changes to it cannot be made independent by the supplied interface. Unlike the pure-function implementation, memoization can retain a long prefix while one copy lags far behind another. The question imposes no constant-storage requirement.
Back to article page
