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. Articles by others on the same topic
There are currently no matching articles.