Tutorial

2. Folds and lazy iteration¶

map, filter and scan_left transform a sequence lazily: constructing an iterator does not run its callbacks. A consumer such as fold_left then pulls values through the chain and combines them into one result. scan_left yields snapshots of the initial accumulator and each updated accumulator, so you can inspect the intermediate steps of a fold.

Callbacks in lazy adapters cannot raise. To carry a failure through the chain, return a Result element and handle it when consuming the iterator.

Chain operations with methods¶

Start with iterated(source) to write transformations from left to right. Each transformation returns a native iterator with the same chaining methods. Finish with to_list() or its alias collect_list() to consume the remaining elements into a List.

iteration_chaining.mojo Download

"""Chain lazy transformations and pass their native iterators to standard adapters."""
from fp.iteration import iterated
from std.collections.string import Codepoint
from std.iter import enumerate, iter
from std.testing import assert_equal


def codepoints_of(text: String) -> List[Codepoint]:
    return List(text.codepoints())


def main() raises:
    var words: List[String] = ["hello", "world"]
    var chars = (
        iterated(words^)
        .flat_map(codepoints_of)
        .to_list()
    )
    assert_equal(chars, List("helloworld".codepoints()))
    print("codepoints:", len(chars))

    # Standard adapters consume the wrapper through IterableOwned.
    var numbered = enumerate(iterated(range(4, 7)))
    var pairs = iterated(numbered^).collect_list()
    assert_equal(pairs, [(0, 4), (1, 5), (2, 6)])
    for pair in pairs:
        print(pair[0], pair[1])

    # Borrow explicitly when the collection should remain available.
    var values: List[Int] = [1, 2, 3]
    var copied = iterated(iter(values)).to_list()
    assert_equal(values, [1, 2, 3])
    assert_equal(copied, values)

Run from the repository root pixi run mojo run -I src docs/examples/iteration_chaining.mojo

Output

codepoints: 10
0 4
1 5
2 6

The first chain consumes words, expands each word into codepoints, and collects ten values. It has the same behavior as collect_list(flat_map(codepoints_of, words^)): each word's codepoint list is built only when that word is reached. The helper still materializes an inner list. Returning a borrowing codepoint iterator from a temporary owned string would require a different ownership contract.

Iter implements native Iterator and IterableOwned, so enumerate consumes it directly. The returned standard adapter can pass through iterated(numbered^) to resume chaining. Native next, consuming for loops, zip, chain and compatible std.itertools adapters work the same way. Each standard operation keeps its own type and ownership requirements.

Pass iterated(values^) to consume a collection, or iterated(iter(values)) to borrow it. Keep borrowed owners alive and unmoved for the duration of the chain. Borrowed sources follow the native iterator's element-copy rules; wrapping does not make them yield owned move-only elements.

Every transformation and terminal consumes its receiver. With a named stream, write stream^.map(f) or stream^.to_list(). A partially consumed iterator continues at its current position. The wrapper adds no buffering or allocation, and lazy methods do not run callbacks until an element is requested.

The method names and callback arguments match the free functions, with the source supplied by the receiver. For example, stream^.fold_left(step, initial) and stream^.reduce(step, initial=initial) preserve the existing fold contracts. scan_left still yields the initial snapshot before reading the source. The free functions remain available, and to_list() and collect_list() are the same consuming operation.

Plain functions, closures and library callables retain their existing constraints. Move a closure with owned state into a lazy method with callback^. Generic raising terminal wrappers pass the error explicitly, as in stream^.fold_left[E=E](step, initial^).

Build a lazy chain and collect it¶

This program keeps the positive values of [-1, 1, 3], doubles them and records running totals. Captured counters show when each callback runs. A second chain filters Optional results and expands each remaining value into a List, and the end of the program shows an order-sensitive fold and an empty reduction.

iteration.mojo Download

"""Lazy selection, ordered reduction, and initial-first snapshots."""
from fp.iteration import fold_left, reduce_optional
from fp.iteration import map, filter, filter_map, flat_map, scan_left, collect_list
from std.testing import assert_equal

def add(var total: Int, var value: Int) -> Int:
    return total + value

def subtract(var total: Int, var value: Int) -> Int:
    return total - value

def main() raises:
    var values: List[Int] = [-1, 1, 3]
    var tested = 0
    var mapped = 0
    var stepped = 0
    var factor = 2

    def positive(value: Int) {mut tested} -> Bool:
        tested += 1
        return value > 0

    def twice(var value: Int) {mut mapped, factor} -> Int:
        mapped += 1
        return value * factor

    def running(var total: Int, var value: Int) {mut stepped} -> Int:
        stepped += 1
        return total + value

    var selected = map(twice, filter(positive, values^))
    var scanned = scan_left(running, 0, selected^)
    assert_equal(tested, 0)
    assert_equal(mapped, 0)
    assert_equal(stepped, 0)
    var snapshots = collect_list(scanned^)
    assert_equal(tested, 3)
    assert_equal(mapped, 2)
    assert_equal(stepped, 2)
    var expected: List[Int] = [0, 2, 8]
    assert_equal(snapshots, expected)
    var checked = 0
    var expanded = 0
    var offset = 10

    def odd(var value: Int) {mut checked} -> Optional[Int]:
        checked += 1
        if value % 2: return Optional(value)
        return None

    def pair(var value: Int) {mut expanded, offset} -> List[Int]:
        expanded += 1
        return [value, value + offset]

    var pairs = flat_map(pair, filter_map(odd, range(1, 4)))
    assert_equal(checked, 0)
    assert_equal(expanded, 0)
    var outputs = collect_list(pairs^)
    var expected_pairs: List[Int] = [1, 11, 3, 13]
    assert_equal(outputs, expected_pairs)
    assert_equal(checked, 3)
    assert_equal(expanded, 2)
    assert_equal(fold_left(subtract, 10, range(1, 4)), 4)
    var empty = reduce_optional(add, range(0))
    assert_equal(Bool(empty), False)
    for i in range(len(snapshots)):
        print(snapshots[i])

Run from the repository root pixi run mojo run -I src docs/examples/iteration.mojo

Output

0
2
8

filter(positive, values^) consumes the list as its source. A range such as range(1, 4) is already an iterator, and iter(values) would borrow the list instead.

Creating filter, map and scan_left pulls nothing, so all three counters are still 0 afterwards. collect_list then pulls every snapshot:

The first snapshot is a copy of the initial 0, before any input is pulled.
The next pull skips -1, doubles 1, and yields 2.
The last pull doubles 3 to 6 and yields the total 8.

Collecting makes three predicate calls, two map calls and two scan steps, and the program prints 0, 2 and 8. If a consumer abandons the chain early, native cleanup destroys the current adapter state and the rest of the owned source; the tail is never evaluated.

The second chain makes three odd calls on range(1, 4) and two pair expansions, and yields [1, 11, 3, 13].

Choose the terminal operation¶

Need	Operation	Empty input
A known initial accumulator	`fold_left` or initialized `reduce`	Returns the initializer
Same input/accumulator type, no initializer	`reduce`	Raises a distinct empty-reduction error
Absence instead of an empty error	`reduce_optional`	Returns native Optional absence
Explicit early termination	`fold_until`	Returns `Continue(initial)`

fold_left(subtract, 10, range(1, 4)) computes ((10 - 1) - 2) - 3 = 4. Folds run in order: they do not reassociate operations, assume numeric types, or reduce SIMD lanes for you. reduce_optional(add, range(0)) returns an empty Optional.

find, any and all stop at the first result that decides the answer. fold_until stops on Break, with no extra pull from the source. Lazy flatten handles empty inner iterators, and exhausts an inner source before it pulls the next outer value.

Know what snapshots and errors cost¶

For n input values, a fully consumed scan yields n + 1 snapshots. Each one is a copy of the accumulator, made with its native Copyable implementation, so keeping every snapshot of a growing List can cost much more than a terminal fold. Only the accumulator needs to be copyable; source elements can move.

Callbacks in lazy adapters cannot raise. To report a failure from inside a lazy chain, return Result elements and finish with collect_results. Terminal folds and searches have separate raising overloads, and a callback's error is never mistaken for the end of the iterator.

Return adapters from generic functions¶

Use MapIterator and ScanIterator in return annotations, and build their values with map and scan_left. The helper's I parameter is the native iterator type, including any source origin. Keeping the exact callback type F preserves its captured state and origins when the adapter is returned.

iteration_generic.mojo Download

"""Return lazy adapters through generic functions with public native type aliases."""
from fp.iteration import MapIterator, ScanIterator, map, scan_left
from std.iter import Iterator, iter, next
from std.testing import assert_equal


def mapped[T: Movable & Deinitable, U: Movable & Deinitable, I: Iterator, //,
           F: def(var T) -> U](var function: F, var source: I) -> MapIterator[T, U, I, F] where I.Element == T:
    return map(function^, source^)


def scanned[A: Copyable & Deinitable, T: Movable & Deinitable, I: Iterator, //,
            F: def(var A, var T) -> A](var function: F, var initial: A, var source: I) -> ScanIterator[A, T, I, F] where I.Element == T:
    return scan_left(function^, initial^, source^)


def main() raises:
    var map_calls = 0
    var scan_calls = 0
    def double(var value: Int) {mut map_calls} -> Int:
        map_calls += 1
        return value * 2
    def add(var total: Int, var value: Int) {mut scan_calls} -> Int:
        scan_calls += 1
        return total + value
    var values: List[Int] = [1, 2, 3]
    var transformed = mapped(double, iter(values))
    var running = scanned(add, 0, transformed^)
    assert_equal(map_calls, 0)
    assert_equal(scan_calls, 0)
    assert_equal(next(running), 0)
    assert_equal(map_calls, 0)
    assert_equal(scan_calls, 0)
    assert_equal(next(running), 2)
    assert_equal(next(running), 6)
    assert_equal(map_calls, 2)
    assert_equal(scan_calls, 2)
    # Abandon the last element without forcing its evaluation.
    _ = running^
    assert_equal(map_calls, 2)
    assert_equal(scan_calls, 2)
    assert_equal(values, [1, 2, 3])
    print("generic lazy snapshots: 0, 2, 6; source preserved")

Run from the repository root pixi run mojo run -I src docs/examples/iteration_generic.mojo

Output

generic lazy snapshots: 0, 2, 6; source preserved

mapped and scanned name their element, result and source types, and call sites infer them; nothing is discovered at run time. After construction both counters are 0. The first next returns the initial snapshot 0 without pulling from the source. The next two return 2 and 6, after two map calls and two scan steps. The program then drops the iterator, so the third value is never mapped, and the borrowed list is still [1, 2, 3]. Keep borrowed sources and the owners of captured state alive and unmoved while the iterator is in use.

On the pinned compiler, keep the T/U and A/T callback parameter names and the minimal constraints shown here. Separate wrappers compose at a concrete call site, but a single generic factory that combines a map and a scan loses callback metadata on Mojo 1.1, so keep them in separate wrappers. See native Mojo boundaries.

Return filtering adapters¶

This generic chain keeps the positive values of [0, 1, 2, 3, 4, 5], turns the even ones into String labels, and expands each label into two outputs. Each helper returns an ordinary lazy adapter with its exact native type and origins. The flat-map factory checks the inner iterator's conformance at compile time, after type inference; the helpers do not inspect callback metadata.

iteration_filtering_generic.mojo Download

"""Generic filtering helpers preserve lazy state and borrowed sources."""
from fp.iteration import FilterIterator, FilterMapIterator, FlatMapIterator, filter, filter_map, flat_map
from std.iter import Iterator, IterableOwned, iter, next
from std.testing import assert_equal

def selected[T: Movable & Deinitable, I: Iterator, //, F: def(T) -> Bool](
    var function: F, var source: I
) -> FilterIterator[T, I, F] where I.Element == T:
    return filter(function^, source^)

def selected_again[T: Movable & Deinitable, I: Iterator, //, F: def(T) -> Bool](
    var function: F, var source: I
) -> FilterIterator[T, I, F] where I.Element == T:
    return selected(function^, source^)

def present[T: Movable & Deinitable, U: Movable & Deinitable, I: Iterator, //, F: def(var T) -> Optional[U]](
    var function: F, var source: I
) -> FilterMapIterator[T, U, I, F] where I.Element == T:
    return filter_map(function^, source^)

def present_again[T: Movable & Deinitable, U: Movable & Deinitable, I: Iterator, //, F: def(var T) -> Optional[U]](
    var function: F, var source: I
) -> FilterMapIterator[T, U, I, F] where I.Element == T:
    return present(function^, source^)

def expanded[T: Movable & Deinitable, U: Movable & Deinitable, I: Iterator, //, F: def(var T) -> U](
    var function: F, var source: I
) -> FlatMapIterator[T, U, I, F] where I.Element == T:
    return flat_map(function^, source^)

def expanded_again[T: Movable & Deinitable, U: Movable & Deinitable, I: Iterator, //, F: def(var T) -> U](
    var function: F, var source: I
) -> FlatMapIterator[T, U, I, F] where I.Element == T:
    return expanded(function^, source^)

def main() raises:
    var predicates = 0
    var optionals = 0
    var expansions = 0
    def positive(value: Int) {mut predicates} -> Bool:
        predicates += 1
        return value > 0
    def even_label(var value: Int) {mut optionals} -> Optional[String]:
        optionals += 1
        if value % 2: return None
        return Optional(String(value))
    def pair(var value: String) {mut expansions} -> List[String]:
        expansions += 1
        return [value.copy(), value + "!"]
    var values: List[Int] = [0, 1, 2, 3, 4, 5]
    var output = expanded_again(pair, present_again(even_label, selected_again(positive, iter(values))))
    assert_equal(predicates, 0)
    assert_equal(optionals, 0)
    assert_equal(expansions, 0)
    assert_equal(next(output), "2")
    assert_equal(next(output), "2!")
    assert_equal(predicates, 3)
    assert_equal(optionals, 2)
    assert_equal(expansions, 1)
    assert_equal(next(output), "4")
    assert_equal(predicates, 5)
    assert_equal(optionals, 4)
    assert_equal(expansions, 2)
    assert_equal(values, [0, 1, 2, 3, 4, 5])
    print("generic filtering: 2, 2!, 4; tail unevaluated")

Run from the repository root pixi run mojo run -I src docs/examples/iteration_filtering_generic.mojo

Output

generic filtering: 2, 2!, 4; tail unevaluated

Construction calls none of the callbacks. Reading "2" and "2!" pulls the source up to 2: three predicate calls, two label calls and one expansion. Reading "4" pulls up to 4 and leaves both the second output "4!" and the source value 5 unevaluated. Dropping the adapter releases its current inner state and remaining owned values without evaluating them, and the borrowed source stays available.

FilterIterator yields the original value it selected.
FilterMapIterator skips only absent Optional results; a present Result holding Err is still an output.
FlatMapIterator keeps the returned inner iterator's origins and ownership until that inner iterator is exhausted or abandoned.

See native Mojo boundaries for the constraints behind this spelling.

Generic terminal calls¶

A terminal wrapper consumes an explicit iterator and borrows the callback. Its raising signature names E, and each forwarding call passes [E=E]; accumulator and element types are still inferred. These native signatures keep the error type through precompiled imports, with no result cast or callable promotion.

terminal_generic.mojo Download

"""Generic terminal wrappers retain the callback's exact typed error."""
from fp.iteration import fold_left
from fp.iteration import find
from std.iter import Iterator, iter
from std.testing import assert_equal


def folded[A: Movable & Deinitable, T: Movable & Deinitable, I: Iterator,
           E: Movable & Deinitable, //, F: def(var A, var T) raises E -> A](
    step: F, var initial: A, var source: I
) raises E -> A where I.Element == T:
    return fold_left[E=E](step, initial^, source^)


def forwarded[A: Movable & Deinitable, T: Movable & Deinitable, I: Iterator,
              E: Movable & Deinitable, //, F: def(var A, var T) raises E -> A](
    step: F, var initial: A, var source: I
) raises E -> A where I.Element == T:
    return folded[E=E](step, initial^, source^)


@fieldwise_init
struct InvalidEntry(Movable):
    var value: Int


def main() raises:
    var calls = 0
    def append(var text: String, var value: Int) raises InvalidEntry {mut calls} -> String:
        calls += 1
        if value < 0: raise InvalidEntry(value)
        return text + String(value)
    var result: String
    try: result = forwarded(append, String("entries:"), range(3))
    except: raise Error("unexpected entry error")
    assert_equal(result, "entries:012")
    assert_equal(calls, 3)
    var inputs: List[Int] = [4, -7, 9]
    var rejected = 0
    try: _ = forwarded(append, String("entries:"), iter(inputs^))
    except error:
        comptime assert type_of(error) == InvalidEntry
        rejected = error.value
    assert_equal(rejected, -7)
    assert_equal(calls, 5)
    def even(value: Int) -> Bool: return value % 2 == 0
    var first = find(even, range(3, 8))
    assert_equal(first.value(), 4)
    print(result, "; rejected:", rejected, "; first even:", first.value())

Run from the repository root pixi run mojo run -I src docs/examples/terminal_generic.mojo

Output

entries:012 ; rejected: -7 ; first even: 4

forwarded(append, String("entries:"), range(3)) returns "entries:012" after three calls. Over [4, -7, 9], append raises InvalidEntry(-7) on the second value. That exact error crosses both wrappers, and 9 is never pulled, so the call count ends at five. find(even, range(3, 8)) returns 4.

Use the non-raising overload when the callback does not raise. The same forwarding rule applies to reduce_optional, both reduce forms, fold_until, find, any and all.

Next, keep success and failure as values with Result transformations. For every operation, see fp.iteration and ControlFlow.