Cache only a requested current element. Merely constructing the cursor, or asking whether it is nonempty, must not fetch a value from the iterator:
def asCursor[T](it: Iter[T]): Cursor[T] = new Cursor[T] {
private var cached: Option[T] = None
def hasCurrent: Boolean = cached.nonEmpty || it.hasNext
def current: T = {
if (cached.isEmpty) {
require(it.hasNext, "empty cursor")
cached = Some(it.next())
}
cached.get
}
def next(): Unit = {
if (cached.nonEmpty) cached = None
else {
require(it.hasNext, "empty cursor")
it.next()
()
}
}
}The abstraction function for the adapter is
it.seq when no value is cached and [cachedValue] ++ it.seq otherwise. Fetching current removes one underlying iterator value but saves it, so the cursor's abstract sequence is unchanged; repeated reads return the same value. Advancing either discards that cache or consumes one uncached iterator value. No following element is prefetched.A too-eager implementation could call
it.next() at construction, or fetch a new element immediately after every advance, even when the client never requests it. That can trigger unnecessary work or nontermination on a difficult stream. This lazy iterator-to-cursor adapter avoids both behaviors and checks the underlying access preconditions itself. The wrapped iterator is assumed to be used exclusively through the adapter; independent external consumption would invalidate the shared-state abstraction.def asIter[T](cur: Cursor[T]): Iter[T] = new Iter[T] {
def hasNext: Boolean = cur.hasCurrent
def next(): T = {
require(cur.hasCurrent, "empty iterator")
val answer = cur.current
cur.next()
answer
}
}The two abstract sequences are identical. A
next call returns the old head and removes it, while hasNext only queries availability. No element is read at construction or during an availability test, and no later element is read while returning the current one. Thus the adapter is not too eager. The source's Cursor.current clause needs the implicit precondition that its sequence is nonempty; taking the head of an empty sequence is undefined. The checks above satisfy that requirement even without relying on the client convention.Map a pure, terminating function only when a value is demanded; use the adapters to obtain the cursor form with caching:
def map[T, U](f: T => U, it: Iter[T]): Iter[U] = new Iter[U] {
def hasNext: Boolean = it.hasNext
def next(): U = {
require(it.hasNext, "empty iterator")
f(it.next())
}
}
def map[T, U](f: T => U, cur: Cursor[T]): Cursor[U] =
asCursor(map(f, asIter(cur)))Each demanded output is the function applied to the corresponding input, preserving order and lazy access even for an infinite sequence. The cursor adapter caches its mapped current value, so repeated reads need not recompute
f. Totality/purity of f is the usual assumption for the mathematical sequence-map postcondition; an exception-throwing or state-changing function would need additional behavioral clauses.Both functions may be named
map because their second parameter types differ, Iter[T] versus Cursor[T]. Method overloading selects the applicable signature; its distinction is not based solely on the return type.A single flag represents whether the only element remains:
def unitIter[T](t: T): Iter[T] = new Iter[T] {
private var available = true
def hasNext: Boolean = available
def next(): T = {
require(available, "empty iterator")
available = false
t
}
}
def unitCursor[T](t: T): Cursor[T] = new Cursor[T] {
private var available = true
def hasCurrent: Boolean = available
def current: T = {
require(available, "empty cursor")
t
}
def next(): Unit = {
require(available, "empty cursor")
available = false
}
}The abstract sequence is
[t] while the flag is true and empty afterward. current leaves it unchanged; either advance consumes its sole element. Renaming both methods to unit would leave identical parameter signatures differing only in result type, which cannot define two such Scala overloads.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.
Use the heap-numbered binary tree with root label zero and children . Its strict descendants in breadth-first search order are . A machine-safe
Node[Int] version stops at the largest representable label:class NumberNode(val label: Int) extends Node[Int] {
require(label >= 0)
def children(): Iter[Node[Int]] = new Iter[Node[Int]] {
private var candidate = 2L * label.toLong + 1L
private val last = candidate + 1L
def hasNext: Boolean = candidate <= last && candidate <= Int.MaxValue
def next(): Node[Int] = {
require(hasNext)
val answer = new NumberNode(candidate.toInt)
candidate += 1L
answer
}
}
}
val traversal = breadthFirst(new NumberNode(0))
var expected = 1
while (expected <= 1000) {
assert(traversal.hasNext)
assert(traversal.next().label == expected)
expected += 1
}The arithmetic is widened before computing child labels, so no negative wrapped labels occur. Repeated
hasNext calls should not skip nodes; a leaf root should produce immediate exhaustion, and uneven finite trees should retain sibling order across parents. A fresh second traversal should start again at one.Literal unbounded increase is impossible with the bounded
Int type. For a genuinely infinite test, change the label and child arithmetic to BigInt; the same construction then has no representational endpoint. The shown finite-prefix test already exercises lazy traversal without allocating the entire very large Int-labelled tree. Articles by others on the same topic
There are currently no matching articles.