= Solution
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
$$
acc=f(\cdots f(f(x,a_1),a_2)\cdots,a_k).
$$
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
$$
\boxed{foreach\text{ visits in order};\quad exists\text{ short-circuits};\quad foldLeft\text{ associates to the left}.}
$$
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>.
Back to article page
