13. Iteration
Taught in Iteration and Loops.
The Iter protocol
Section titled “The Iter protocol”Taught in Collections.
Iter<T> in std::iter is the one iteration protocol. It is a push iterator:
interface Iter<T> fn each_while(collection: self, yield: (T) -> Bool) -> Bool open fn known_count(_collection: self) -> Maybe<Int> None end open fn is_infinite(_collection: self) -> Bool False end end
each_whilewalks the source and passes each element toyield, which returnsFalseto ask it to stop.each_whilereturnsTruewhen the source ran out andFalsewhen a consumer stopped it. This is the whole early-termination mechanism:Iter.take(3)stops an infinite source by refusing a fourth element. It is Go’siter.Seqshape.known_countisSome(n)when the source knows its length without being walked, andNoneotherwise.Iter.countconsults it.List,Vector,Map,Set,Maybeand bounded ranges whose element type can count steps override it.is_infiniteisTruewhen the source never ends on its own (Infinite iterators).each_whilereads a value it never changes, so an iterator can be run again. A stream’s iterators (Reader.lines,Reader.chunks,io.lines) are the exception: they read the stream as they run (std::io).- An
Iter<T>is an ordinary value: a binding, a parameter, a result, a field, a tuple or record part, a payload, a list element and a capture can hold one. Holding it runs nothing, and each consumer runs it from its start. - Any source stands where an
Iter<T>is expected (aList,Vector,Set,Map,String,Bytes,Maybe, range, or a type with animpl Iter) and keeps its ownknown_countthere.
Map<K, V> is an Iter<(K, V)>, String an Iter<String> of grapheme
clusters, and Maybe<T> an Iter<T> of zero or one element. A range is an
Iter when its element type is Discrete (§3 Range literals). What each std
source yields is in std::iter.
A collection is an Iter; an Iter is not a collection. An Iter<T>
where a collection is expected (an annotation, an argument, a field, an
element, a result) is a type error whose help names the function that
collects it: type mismatch: expected List<Int>, got Iter<Int>, with an Iter is not a collection; collect it into one with `|> Iter.to_list()` . The same holds for
every interface: a value of interface type never stands where an implementor is
expected.
Infinite iterators
Section titled “Infinite iterators”is_infinite returns True for Iter.repeat, Iter.from, Iter.iterate
(whose step cannot break), Range.from, Range.naturals, Range.step_by of
an unbounded range whose step moves, and Iter.cycle of a source that is
infinite or knows a non-zero count. A type of the program returns False
unless its impl Iter writes is_infinite. Each adapter carries the
result when the pipeline is built: map over an infinite source is
infinite, and take never is. When in doubt the result is False.
A terminal that has to reach the end of its source (to_list, count,
sort, sum, …) asks is_infinite first and traps on True, naming the
terminal and the source, at the program’s line:
line 6: `Iter.to_list` of an infinite iterator (`Iter.repeat`) never finishes; limit it with `Iter.take` or `Iter.take_while`
A terminal that may stop early (first, find, any_match, …) does not trap.
An iterator that never ends without saying so (a type that does not write
is_infinite, a take_while whose predicate never fails) runs until
something stops it. std::iter lists when each adapter is
infinite and which terminals trap.
When the whole pipeline is written where the terminal is, the checker reports the trap as a compile error, with the same text, at the terminal, and a note at the source:
fn coins(coin: Int) -> List<Int> coin |> Iter.repeat() |> Iter.to_list() // error: `Iter.to_list` of an infinite iterator (`Iter.repeat`) never finishes; ... end
- The check follows pipes, nested calls (
Iter.to_list(Iter.map(Iter.from(0), f))) and local bindings whose value is such a pipeline, through any number of them. - It reads only what the source spells: a
Range.from, aRange.step_byof aRange.fromorRange.naturalsby a literal step other than 0,Iter.chunkswith a literal size above 0, andIter.cycleof an infinite source or of a non-empty list, vector, set or map literal. - A callback that holds
breakorcontinue, or one it cannot see into, ends the check, astakeandtake_whiledo. - A parameter, a field, a
once, a function’s result and a program’simpl Iterare not followed; the run-time trap still catches them.
Laziness and fusion
Section titled “Laziness and fusion”Every generic iteration algorithm is an owner function of Iter over any
Iter<T>: Iter.map, Iter.filter, Iter.reduce, Iter.count, and the rest
(std::iter). They are owner functions, not interface
functions, and do not dispatch; known_count and is_infinite are the only
dispatched defaults.
- Adapters are lazy.
map,filter,take,flat_mapand the other adapters return a new iterator and run nothing. A chain of them fuses into one pass over the source, with no intermediate collection. - Terminals consume.
reduce,each,find,count,sortand the materializersto_list,to_vector,to_set,to_mapandreverserun the pipeline. - There are no eager collection adapters.
List.mapandSet.filterdo not exist; a container from a chain is an explicit materialize step:Iter.map(xs, f) |> Iter.to_list(). AnIter<String>is joined withString.join. - Container-specific operations stay on the container’s owner: the work
that reads or rebuilds a container’s structure, such as
Map.map_values,Set.union,List.concat,Vector.get,Map.size,String.splitandString.reverse. breakandcontinuein an adapter’s callback act through the fused pipeline on the consuming terminal.Iter.zippulls its right operand one element at a time, as Go’siter.Pulldoes, since two sources cannot both own the loop. It is the only adapter that pays a coroutine handoff per element, and it works over sources unbounded on either side.
Custom Iters
Section titled “Custom Iters”A type implements Iter<T> by writing each_while: walk the structure, pass
each element to yield, and stop as soon as yield returns False. Every
Iter owner function then works on it.
struct Countdown remaining: Int end impl Iter for Countdown fn each_while(collection: Countdown, yield: (Int) -> Bool) -> Bool n = collection.remaining case n <= 0 -> True yield(n) -> each_while(Countdown{remaining: n - 1}, yield) _ -> False end end end fn main() dbg Countdown{remaining: 3} |> Iter.map(&(&1 * 10)) |> Iter.to_list() // [30, 20, 10] dbg Countdown{remaining: 3} |> Iter.sum() // 6 end
Taught in Iteration and Loops.
Iter.loop(start, step) calls step with a state, start first, and takes
its result as the next state, until a break. import std::iter.Iter.{loop} allows the bare loop.
fn main() countdown = Iter.loop(5, fn n -> if n == 0 then break n n - 1 end) dbg countdown // 0 end
- The callback’s type is
(S) -> S. Its result is the next state.continuegoes round again with the state unchanged, and takes no value (§9breakandcontinue). - The starting state is
from, written before the callback:Iter.loop(5, fn n -> ...),Iter.loop(5, step). It fixesS. A loop with state and no starting state isexpected 2 arguments, got 1. break valueends the loop withvalue, which has typeS:break "hello"inIter.loop(5, fn n -> ...)isbreak value type mismatch: expected Int, got String.- Bare
breakends the loop with the state this round started with. A binding in the body that shadows the parameter does not change it. - A stateless callback (
fn -> ...) has stateUnit. Its body’s result isUnit, everybreakin it is bare orbreak Unit, and the loop returnsUnit. The call takes the callback alone,Iter.loop(fn -> ...). A starting state beside it isa stateless `Iter.loop` takes no starting state. returnin the callback exits the callback.- A loop that never breaks. A callback with no
breakof its own (abreakinside a nested lambda orfnbelongs to that callback) never finishes: only a trap, its task’s cancellation or the end of the process stops it. A statement after it is the errorunreachable code after a loop that never breaks. A binding of it is accepted, and nothing after it runs. - Each round is a safe point (§16), and the loop runs in constant stack space (§7 Tail-call optimization).
import std::io fn main() // stateless: echo lines until "quit" or the end of the input Iter.loop(fn -> Ok(Some(line)) = io.read_line() else break if line == "quit" then break io.print(line) end) end
Callbacks that take break and continue
Section titled “Callbacks that take break and continue”Taught in Iteration and Loops.
break and continue work in the callbacks of a closed set of functions:
Iter.map, Iter.scan, Iter.filter, Iter.take_while, Iter.drop_while,
Iter.flat_map, Iter.iterate, Iter.reduce, Iter.map_reduce,
Iter.each, Iter.find, Iter.any_match, Iter.all_match, Map.map_values,
Map.map_keys and Iter.loop.
A callback’s result is its result for this element. continue skips the
element. break stops the iteration with what has accumulated. break value
gives value as this element’s result and then stops. The signal they send has
no spelling in the language: it is not a type, and nothing imports or matches
it.
| Function | value in break value | continue | bare break |
|---|---|---|---|
map | this element’s output, emitted | no output | stops; outputs so far |
filter | the keep decision (break True keeps it) | drops it | stops |
reduce | the accumulator | accumulator unchanged | the accumulator so far |
find, any_match, all_match | the predicate’s result | skips | None, False, True |
drop_while | the drop decision: break False emits this element and ends | drops it | ends with nothing more |
flat_map | this element’s expansion, emitted | no output | stops |
scan | the new state, yielded | yields nothing, keeps the state | ends without yielding |
map_reduce | (next_state, output), kept | no output, keeps the state | the state and outputs so far |
Map.map_values, Map.map_keys | the entry’s new value or key | leaves the entry out | the entries made so far |
Iter.loop | the loop’s value | the same state again | the state this round started with |
Iter.iterate | the last element, emitted | a compile error | ends without emitting |
continue in an Iter.iterate step, written in its lambda or in a named
function passed as the step, is the error `continue` in an `Iter.iterate` step has no next state to go on to: the step's answer is the next state
at the continue, or at the function’s name; skip states with
Iter.iterate(seed, step) |> Iter.filter(keep).
fn main() names = Iter.map(["ann", "", "bo", "end", "cy"], fn name -> if name == "" then continue if name == "end" then break name end) |> Iter.to_list() dbg names // ["ann", "bo"] end
Named Functions as Callbacks
Section titled “Named Functions as Callbacks”Taught in Iteration and Loops.
A named function passes as a callback wherever a function type fits:
Iter.map(numbers, double). A named function may use break and continue
in its body; its result type stays the plain value type.
fn sum_valid(total: Int, value: Int) -> Int if value < 0 then continue if total > 1000 then break total total + value end fn main() dbg Iter.reduce([1, -2, 3], 0, sum_valid) // 4 end
Using break or continue makes a function iter-sensitive. It is then used
in one way only: passed as an iteration callback itself, positional, by name or
piped (Iter.map(xs, keep), Iter.find(xs, f: is_big), xs |> Iter.map(keep)).
A fold or loop takes its starting value before the callback:
Iter.reduce(values, 0, sum_valid).
-
Any call of it is an error at the call, since its signal would cross the caller: as the whole body of a callback lambda (
fn x -> keep(x)) or capture (&keep(&1)), after a binding, in an arm, as an argument or operand, in another function, in adeferor aconcurrentblock, or outside every callback. So is naming it as a value (f = keep,[keep]). -
The error suggests passing the function, in a call its parameters fit: the iteration whose callback holds the call, otherwise
Iter.mapfor one parameter, orIter.reduceafter a starting value for two whose first parameter’s type is its result’s:`keep` uses `continue`, so it cannot be called: pass it as an iteration callback itself, as in `Iter.map(xs, keep)` `add_until_zero` uses `break`, so it cannot be called: pass it as an iteration callback itself, as in `Iter.reduce(xs, <start>, add_until_zero)`Inside a callback the help is
to decide in this callback instead, return a `Maybe` or an enum from `keep` and write `continue` here. -
A
breakorcontinuein a lambda or capture that is not itself an iteration callback, in a nestedfn, or directly in aconcurrentblock is an error (§9breakandcontinue). -
An iter-sensitive function may be
pub. Which ofbreakandcontinueit uses is part of how other files may use it, and their uses are checked as the declaring file’s are.