= Solution
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
$$
\mathrm{result}=f(\cdots f(f(x,a_1),a_2)\cdots,a_j),
$$
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.
$$
\boxed{\operatorname{foreach}:\text{ordered consumption};\quad\operatorname{exists}:\text{short-circuit search};\quad\operatorname{foldLeft}:\text{left-associated accumulation}.}
$$
With constant-cost callbacks and <iterator> operations, full consumption costs $\Theta(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.
Back to article page
