Skip to content

13. Iteration

Taught in Iteration and Loops.

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_while walks the source and passes each element to yield, which returns False to ask it to stop. each_while returns True when the source ran out and False when 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’s iter.Seq shape.
  • known_count is Some(n) when the source knows its length without being walked, and None otherwise. Iter.count consults it. List, Vector, Map, Set, Maybe and bounded ranges whose element type can count steps override it.
  • is_infinite is True when the source never ends on its own (Infinite iterators).
  • each_while reads 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 (a List, Vector, Set, Map, String, Bytes, Maybe, range, or a type with an impl Iter) and keeps its own known_count there.

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.

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, a Range.step_by of a Range.from or Range.naturals by a literal step other than 0, Iter.chunks with a literal size above 0, and Iter.cycle of an infinite source or of a non-empty list, vector, set or map literal.
  • A callback that holds break or continue, or one it cannot see into, ends the check, as take and take_while do.
  • A parameter, a field, a once, a function’s result and a program’s impl Iter are not followed; the run-time trap still catches them.

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_map and 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, sort and the materializers to_list, to_vector, to_set, to_map and reverse run the pipeline.
  • There are no eager collection adapters. List.map and Set.filter do not exist; a container from a chain is an explicit materialize step: Iter.map(xs, f) |> Iter.to_list(). An Iter<String> is joined with String.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.split and String.reverse.
  • break and continue in an adapter’s callback act through the fused pipeline on the consuming terminal.
  • Iter.zip pulls its right operand one element at a time, as Go’s iter.Pull does, 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.

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. continue goes round again with the state unchanged, and takes no value (§9 break and continue).
  • The starting state is from, written before the callback: Iter.loop(5, fn n -> ...), Iter.loop(5, step). It fixes S. A loop with state and no starting state is expected 2 arguments, got 1.
  • break value ends the loop with value, which has type S: break "hello" in Iter.loop(5, fn n -> ...) is break value type mismatch: expected Int, got String.
  • Bare break ends 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 state Unit. Its body’s result is Unit, every break in it is bare or break Unit, and the loop returns Unit. The call takes the callback alone, Iter.loop(fn -> ...). A starting state beside it is a stateless `Iter.loop` takes no starting state.
  • return in the callback exits the callback.
  • A loop that never breaks. A callback with no break of its own (a break inside a nested lambda or fn belongs 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 error unreachable 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

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.

Functionvalue in break valuecontinuebare break
mapthis element’s output, emittedno outputstops; outputs so far
filterthe keep decision (break True keeps it)drops itstops
reducethe accumulatoraccumulator unchangedthe accumulator so far
find, any_match, all_matchthe predicate’s resultskipsNone, False, True
drop_whilethe drop decision: break False emits this element and endsdrops itends with nothing more
flat_mapthis element’s expansion, emittedno outputstops
scanthe new state, yieldedyields nothing, keeps the stateends without yielding
map_reduce(next_state, output), keptno output, keeps the statethe state and outputs so far
Map.map_values, Map.map_keysthe entry’s new value or keyleaves the entry outthe entries made so far
Iter.loopthe loop’s valuethe same state againthe state this round started with
Iter.iteratethe last element, emitteda compile errorends 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

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 a defer or a concurrent block, 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.map for one parameter, or Iter.reduce after 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 break or continue in a lambda or capture that is not itself an iteration callback, in a nested fn, or directly in a concurrent block is an error (§9 break and continue).

  • An iter-sensitive function may be pub. Which of break and continue it uses is part of how other files may use it, and their uses are checked as the declaring file’s are.