def cat[T](t: Iter[T], u: Iter[T]): Iter[T] = new Iter[T] {
def hasNext: Boolean = t.hasNext || u.hasNext
def next(): T = {
if (t.hasNext) t.next()
else {
require(u.hasNext, "empty iterator")
u.next()
}
}
}
def cat[T](t: Cursor[T], u: Cursor[T]): Cursor[T] = new Cursor[T] {
def hasCurrent: Boolean = t.hasCurrent || u.hasCurrent
def current: T = {
if (t.hasCurrent) t.current
else {
require(u.hasCurrent, "empty cursor")
u.current
}
}
def next(): Unit = {
if (t.hasCurrent) t.next()
else {
require(u.hasCurrent, "empty cursor")
u.next()
}
}
}Assume the two destructive inputs have noninterfering states; in particular, passing the same iterator twice does not create a replayable copy of its original sequence. Fresh independent iterators provide that behavior. Under this ownership condition, the abstraction function is always the concatenation
t.seq ++ u.seq. Consumption from t removes the concatenation's head; once t is empty, consumption from u does so. Availability tests short-circuit, so an infinite first sequence never unnecessarily touches the second.For finite lengths , under a client loop with one availability test and one advance per element, the iterator version directly invokes
t.hasNext times, including the final false test. For a cursor client with one availability test, one current read and one advance per element, the corresponding count is . These count calls made by the shown adapters, not extra checks hidden inside arbitrary underlying methods. A client can repeat availability/current queries arbitrarily often, so no bound depending only on applies without such a client protocol.Cache a permanent “first input exhausted” flag after the first negative test to avoid repeated queries to
t while traversing u; this reduces the dependence to first-input queries under the same protocols. Availability caching can reduce additional repeated checks. The flag is sound because an iterator's consumed sequence does not spontaneously grow again.Keep a FIFO queue of pending child iterators, ordered by the breadth-first order of their parents. Defer even the call creating a node's children until that iterator reaches the front and is needed:
def breadthFirst[T](node: Node[T]): Iter[Node[T]] = {
def childrenLater(n: Node[T]): Iter[Node[T]] = new Iter[Node[T]] {
private lazy val children = n.children()
def hasNext: Boolean = children.hasNext
def next(): Node[T] = {
require(children.hasNext, "empty child iterator")
children.next()
}
}
val pending = scala.collection.mutable.Queue.empty[Iter[Node[T]]]
pending.enqueue(childrenLater(node))
new Iter[Node[T]] {
private def normalize(): Unit = {
while (pending.nonEmpty && !pending.head.hasNext) pending.dequeue()
}
def hasNext: Boolean = {
normalize()
pending.nonEmpty
}
def next(): Node[T] = {
normalize()
require(pending.nonEmpty, "no more descendants")
val answer = pending.head.next()
pending.enqueue(childrenLater(answer))
answer
}
}
}Here “descendants” excludes the supplied root: the first output is its first child. A self-inclusive convention can prepend
unitIter(node) without changing the traversal logic. The queue invariant says its iterators enumerate the still-unreported children of already encountered parents, in parent breadth-first order. Consuming one child appends that child's deferred iterator after all earlier parents' pending children. Exhausted child iterators contribute nothing and can be discarded. This proves increasing depth and sibling order without constructing a complete level in advance.This lazy breadth-first traversal with child iterators never eagerly materializes all children or the whole tree. A finite prefix can therefore be traversed on a genuinely infinite tree. As with any strict breadth-first ordering, an infinite earlier level prevents reaching a deeper level; no algorithm can place a deeper node after every member of an infinite earlier level at a finite output position. For a locally finite tree, every finite-depth level is finite and each descendant is eventually reached, assuming the underlying iterator operations terminate. Fresh child iterators and exclusive ownership of consumed iterator states are essential to this argument.
Scala 2.12 iterator API documentation 2026-10-24
Archived official Scala API. Relevant locators: the abstract members
hasNext and next, the exhaustion exception, and the consuming nature of iterators. The associated historical overview is Collections for Scala 2.8–2.12: Iterators. Scala 2.12 types specification 2026-10-24
Scala 2.13 iterator API documentation 2026-10-24
Shared iterator consumption 2026-10-24
Stateless iterator 2026-10-24
An iterator whose future observable sequence can be produced without changing cursor state. An infinite constant sequence is an example: removing its first element leaves the same sequence. A permanently empty iterator is another. Such cases show why an iterator interface does not logically force every implementing object to be mutable, although ordinary finite nonempty traversals need progress state somewhere.
State machine 2026-10-31
A computational model with an internal state and transition rule, together with an initial state and optional observation and stopping functions. The state space need not be finite; a finite-state machine is the special case with finitely many states. A trace records observations along transitions. An interface providing only reset, update, stopping and observation operations does not by itself provide copying or rollback; a trace iterator can revisit saved observations without reversing machine effects.