#Iterators

Status: standard library specification draft.

This chapter defines the part of std.iter that lib/std writes in ordinary hd over the language tier:

the iterator adapters filter, take, enumerate, map, fold, and collect, with their laziness and ordering;
the adapters skip, take_while, zip, chain, and flat_map, and the draining any, all, find, and count;
the FromIterator trait and the collections collect builds: List, Map, Result, and T?;
map on List[T] and on T?.

The language tier keeps what the compiler knows by name (Iteration Protocols):

Item	Why it stays in the language tier
`Iterator[T]`	the prelude cursor trait that `for` advances through `next`
`ListIter[T]` and `MapEntries[K, V]`	the cursor types of a list's and a map's `iter`, which Built-In Methods names
`Iterable[T]` and its impls	the lang item that drives `for` and comprehensions; `List`, `Map`, and the iterable ranges implement it, not `Iterator`

Nothing in the language tier names an adapter, collect, or FromIterator. collect's default target, List[T], is an ordinary type-argument default, which needs no compiler knowledge of collect.

#Collection Cursors

A list's iter returns a ListIter[T] and a map's a MapEntries[K, V], as their Iterable implementations' IntoIter:

use std.iter.ListIter

fn evens(values: List[i32]) -> List[i32]:
    let cursor: ListIter[i32] = values.iter()
    cursor.filter(fn(value): value % 2 == 0).collect()

std-iter.cursor.liststd.iter declares ListIter[T], whose next yields the list's elements in order, as the list held them when iter ran.
std-iter.cursor.mapstd.iter declares MapEntries[K < Eq & Hash, V], whose next yields the map's entries as (K, V) tuples in the map's iteration order.
std-iter.cursor.privateBoth have private fields, so only iter makes one, and both iterate a snapshot (Iterator Snapshots).

#Optional Cursors

Option iterates without building a list for its payload.

std-iter.option.iterable-cursorOption[T] implements Iterable[T], with std.option.OptionIter[T] as its IntoIter.
std-iter.option.cursor.someA .Some(value) cursor yields value once, then .None on every later call.
std-iter.option.cursor.noneA .None cursor yields .None on every call.
std-iter.option.cursor.independentEach iter call returns an independent cursor and leaves the optional unchanged.

#Iterator Factory

from_fn wraps a step closure in the concrete FromFn[T] cursor.

std-iter.from-fn.valuestd.iter.from_fn[T](step: fn() -> T?) -> FromFn[T] returns a cursor storing the closure.
std-iter.from-fn.every-nextEach next call on FromFn[T] calls its stored closure, including calls after .None.

#Iterator Adapters

The prelude Iterator[T] also has iterator adapters: methods that wrap an iterator in a new one, or drain it.

fn first_evens(values: List[i32]) -> List[(usize, i32)]:
    values.iter().filter(fn(value): value % 2 == 0).enumerate().take(2).collect()

Rule	Method	Result
`filter`	`fn filter(self, keep: fn(T) -> bool) -> Filter[Self, T]`	a new iterator over the items of `self` for which `keep` returns `true`
`take`	`fn take(self, count: usize) -> Take[Self, T]`	a new iterator over the first `count` items of `self`, or fewer when `self` ends first
`enumerate`	`fn enumerate(self) -> Enumerate[Self, T]`	a new iterator over `(index, item)` pairs, with `usize` indices counting from `0`
`map`	`fn map[U](self, transform: fn(T) -> U) -> MapIter[Self, T, U]`	a new iterator over `transform(item)` for each item of `self`, in order
std-iter.adapter.fold.value`fold`	`fn fold[A, R](self, initial: A, step: fn(A, T) -> A $ R) -> A $ R`	the accumulator after `step` has combined it with each remaining item of `self`, in order, starting from `initial`
std-iter.adapter.collect.value-defaulted`collect`	`fn collect[C < FromIterator[T] = List[T]](self) -> C`	a `C` built from the remaining items of `self`, as What Collect Builds specifies

std-iter.adapter.filter.valueThe filter default method has signature fn filter(self, keep: fn(T) -> bool) -> Filter[Self, T].
std-iter.adapter.take.valueThe take default method has signature fn take(self, count: usize) -> Take[Self, T].
std-iter.adapter.enumerate.valueThe enumerate default method has signature fn enumerate(self) -> Enumerate[Self, T].
std-iter.adapter.map.valueThe map default method has signature fn map[U](self, transform: fn(T) -> U) -> MapIter[Self, T, U].
std-iter.adapter.skip.valueThe skip default method has signature fn skip(self, count: usize) -> Skip[Self, T].
std-iter.adapter.take-while.valueThe take_while default method has signature fn take_while(self, keep: fn(T) -> bool) -> TakeWhile[Self, T].
std-iter.adapter.zip.valueThe zip default method has signature fn zip[U, J < Iterable[U]](self, other: J) -> Zip[Self, T, U].
std-iter.adapter.chain.valueThe chain default method has signature fn chain[J < Iterable[T]](self, other: J) -> Chain[Self, T].
std-iter.adapter.flat-map.owned-iterableThe flat_map default method has signature fn flat_map[U, J < Iterable[U]](self, transform: fn(T) -> J) -> FlatMap[Self, T, U, J].
std-iter.adapter.trait-defaultsAdapters are default methods of the prelude Iterator[T] trait and require no import.
std-iter.adapter.lazyCalling filter, take, or enumerate does not advance self.
std-iter.adapter.lazy.mapCalling map does not advance self either.
std-iter.adapter.lazy.stored-sourceAn adapter advances its stored source only when its own next is called.
std-iter.adapter.take.limitThe iterator that take returns calls next on self at most count times.
std-iter.adapter.fold.owned-drainfold advances self until next returns .None, which exhausts the owned cursor.
std-iter.adapter.owned-sourceLazy adapters take self by value and store that source value in their returned concrete adapter.
std-iter.adapter.mutable-reference-forwardingA mutable reference to an I < Iterator[T] implements Iterator[T] by forwarding next to the referenced cursor.
std-iter.adapter.draining-valueDraining methods take self by value and advance their owned cursor; passing a mutable cursor reference advances the referenced cursor instead.
std-iter.adapter.named-layoutEach adapter is a named generic struct holding its source and its callback or traversal state.
std-iter.adapter.dyn-bridgeDynIterator[T] is an ordinary concrete cursor storing an erased mutable iterator reference and forwarding next to it.
std-iter.adapter.dyn-forwardingInherent adapter and draining methods on dyn Iterator[T] take &mut self and delegate to a DynIterator[T] holding that reference.
std-iter.adapter.callback-rowThe keep callback has the empty row. A function value whose row lists a requirement key does not fit it. Error: type-mismatch.
std-iter.adapter.callback-row.mapThe transform callback of map has the empty row too.
std-iter.adapter.fold.rowThe step callback of fold may have a requirement row R, and fold then requires R.
std-iter.adapter.callback-row.captureA keep or transform closure whose body uses a requirement key has that key in its row, even inside a $.with block. So it does not fit. Error: type-mismatch.

Error example

use std.iter.FromFn

trait Logger

fn noisy(value: i32) -> bool $ Logger:
    value > 0

fn positives(values: List[i32]) -> List[i32] $ Logger:
    values.iter().filter(noisy).collect()  # error: type-mismatch

fn scoped(values: List[i32], logger: *dyn Logger) -> List[i32]:
    $.with(Logger=logger):
        values.iter().filter(fn(value): noisy(value)).collect()  # error: type-mismatch

fn drain(source: FromFn[i32]) -> List[i32]:
    source.collect()

A callback that needs a provider captures the provider value from $.use outside the closure, so its row stays empty:

trait Logger:
    fn level(self) -> i32

fn above_level(values: List[i32]) -> List[i32] $ Logger:
    let logger: *dyn Logger = $.use(Logger)
    values.iter().filter(fn(value): value > logger.level()).collect()

Why. A lazy adapter's iterator calls keep or transform from its next, whose row is empty, so a stored callback cannot wait for providers. fold calls step before it returns, so the row passes through.

#More Adapters

Iterator[T] also has adapters that skip, stop, pair, and join items, and draining methods that search or count them:

fn body(lines: List[string]) -> List[string]:
    lines.iter().skip(1).take_while(fn(line: string) -> bool: line != "").collect()

fn labeled(names: List[string]) -> List[(i32, string)]:
    [1, 2, 3].iter().zip(names).collect()

fn has_blank(lines: List[string]) -> bool:
    lines.iter().any(fn(line: string) -> bool: line.trim() == "")

Rule	Method	Result
`skip`	`fn skip(self, count: usize) -> Skip[Self, T]`	a new iterator over the items of `self` after the first `count`
`take_while`	`fn take_while(self, keep: fn(T) -> bool) -> TakeWhile[Self, T]`	a new iterator over the items of `self` before the first one for which `keep` returns `false`
`zip`	`fn zip[U, J < Iterable[U]](self, other: J) -> Zip[Self, T, U]`	a new iterator over pairs of the items of `self` and `other` at the same position, which ends when either ends
`chain`	`fn chain[J < Iterable[T]](self, other: J) -> Chain[Self, T]`	a new iterator over the items of `self`, then those of `other`
`flat_map`	`fn flat_map[U, J < Iterable[U]](self, transform: fn(T) -> J) -> FlatMap[Self, T, U, J]`	a new iterator over the items of each iterable that `transform(item)` returns, in order
std-iter.adapter.any.value`any`	`fn any(self, test: fn(T) -> bool) -> bool`	whether `test` returns `true` for some remaining item of `self`
std-iter.adapter.all.value`all`	`fn all(self, test: fn(T) -> bool) -> bool`	whether `test` returns `true` for every remaining item of `self`
std-iter.adapter.find.value`find`	`fn find(self, test: fn(T) -> bool) -> T?`	the first remaining item of `self` for which `test` returns `true`, or `.None`
std-iter.adapter.count.value`count`	`fn count(self) -> usize`	the number of remaining items of `self`
std-iter.adapter.sum.numeric-target`sum`	`fn sum[S < Sum[T]](self) -> S`	the target built from the remaining items

std-iter.adapter.lazy.moreCalling skip, take_while, zip, chain, or flat_map advances no iterator. The returned iterator pulls only when its own next is called.
std-iter.adapter.skip.first-nextThe first next call of skip's iterator reads and drops up to count items of self before it reads the item it returns.
std-iter.adapter.take-while.stoptake_while's iterator reads and drops the first item that keep rejects, and calls next on self no more after it.
std-iter.adapter.iterable-argzip and chain call other.iter() once, when they are called, and read the items of other from that iterator only.
std-iter.adapter.iterable-arg.iterator-boundAn iterator argument without an Iterable[T] implementation is an error, by flow.for.iterator.iterable-bound. Error: unsatisfied-trait-bound.
std-iter.adapter.zip-iterable.orderzip's iterator calls next on self first, and on the iterator of other only when self gave an item. So when self ends first, other loses no item.
std-iter.adapter.chain-iterable.orderchain's iterator calls next on the iterator of other only after self has returned .None, and on self no more after that.
std-iter.adapter.stop-early.ownedany, all, and find advance their owned cursor only until an item decides the result, and leave its remaining items unread.
std-iter.adapter.exhaustedOn an exhausted iterator, any is false, all is true, find is .None, and count is 0.
std-iter.adapter.count.owned-draincount advances self until next returns .None, which exhausts the owned cursor.
std-iter.adapter.callback-row.moreThe callbacks of these methods have the empty row, as filter's keep does. A function value whose row lists a requirement key does not fit. Error: type-mismatch.
std-iter.sum.numeric-orderThe numeric Sum[T] implementation starts at T::zero() and adds each remaining item in order.
std-iter.sum.numeric-overflowAn integer numeric sum outside the range of T panics, as + does. Panic: integer-overflow.
std-iter.sum.owned-drainThe numeric sum implementation advances its owned cursor until next returns .None.
std-iter.sum.target-boundsum requires a result type implementing Sum[T]. Error: unsatisfied-trait-bound.
std-iter.adapter.flat-map.open-onceflat_map calls iter() once on each transformed result, only when that result is reached.
std-iter.adapter.flat-map.drain-innerIt drains that cursor before transforming the next source item, skipping empty results.

Error example

fn joined(first: List[i32], rest: &mut dyn Iterator[i32]) -> List[i32]:
    first.iter().chain(rest).collect()  # error: unsatisfied-trait-bound

fn joined_eagerly(first: List[i32], rest: *mut dyn Iterator[i32]) -> List[i32]:
    let tail: List[i32] = rest.collect()
    first.iter().chain(tail).collect()

Note. An iterator's remaining items pass as a list, collected first, as joined_eagerly shows. An iterator that may never end goes in the receiver position instead: rest.zip(first) pairs the same items in swapped order.

Note. [1, 2, 3].iter().sum() is 6, and [0.5, 0.25].iter().sum() is 0.75. A list has the same method: std-collections.helper.sum.

Why. The names and the pulling order are Rust's, so zip and take_while drop the same items there and here. zip and chain take any Iterable, as Rust's two take any IntoIterator, so a list, set, or range passes directly. I is a bounded type parameter, so other.iter() is dispatched statically, with no trait value.

#Borrowed Cursors

by_ref creates a value cursor that advances an existing cursor:

fn first_two[I < Iterator[i32]](source: *mut I) -> List[i32]:
    source.by_ref().take(2).collect()

std-iter.by-ref.methodIterator[T].by_ref(&mut self) -> ByRef[Self] returns a borrowed cursor.
std-iter.by-ref.layoutByRef[I] stores one mutable reference to its source cursor.
std-iter.by-ref.nextFor I < Iterator[T], ByRef[I] implements Iterator[T] by forwarding next to that source.
std-iter.by-ref.progressAdapting or draining a ByRef value advances the original cursor.
std-iter.by-ref.permissionCalling by_ref requires a writable cursor place or a mutable reference. Error: not-writable.

#Numeric Aggregation

Sum[T] and Product[T] build an aggregate from cursor items.

std-iter.sum.traitSum[T] declares fn sum[I < Iterator[T]](items: I) -> Self.
std-iter.product.traitProduct[T] declares fn product[I < Iterator[T]](items: I) -> Self.
std-iter.sum.numericEvery numeric T implements Sum[T].
std-iter.product.numericEvery numeric T implements Product[T].
std-iter.sum.methodIterator[T] provides fn sum[S < Sum[T]](self) -> S.
std-iter.product.methodIterator[T] provides fn product[P < Product[T]](self) -> P.
std-iter.aggregate.targetThe expected result type or an explicit type argument can determine the aggregate target.
std-iter.aggregate.inferenceAn aggregate target has no type-argument default and follows ordinary bound inference.
std-iter.aggregate.unsolvedAn unsolved aggregate target requires an expected type or an explicit type argument. Error: cannot-infer-type.
std-iter.product.numeric-orderThe numeric Product[T] implementation starts at T::one() and multiplies each remaining item in order.
std-iter.product.numeric-overflowAn integer numeric product outside the range of T panics, as * does. Panic: integer-overflow.
std-iter.product.owned-drainThe numeric product implementation advances its owned cursor until next returns .None.
std-iter.product.target-boundproduct requires a result type implementing Product[T]. Error: unsatisfied-trait-bound.

fn total(values: List[i32]) -> i32:
    values.iter().sum::[i32]()

fn multiplied(values: List[i32]) -> i32:
    let result: i32 = values.iter().product()
    result

#What Collect Builds

collect builds the collection that the expected type names:

fn parse_port(text: string) -> Result[usize, string]:
    .Ok(text.len())

fn index(names: List[string]) -> Map[string, usize]:
    names.iter().map(fn(name): (name, name.len())).collect()

fn parse_all(lines: List[string]) -> Result[List[usize], string]:
    lines.iter().map(parse_port).collect()

fn count(values: List[i32]) -> usize:
    copied := values.iter().collect()
    copied.len()

The collection being built implements the std.iter trait FromIterator[T]:

trait FromIterator[T]:
    fn from_iter[I < Iterator[T]](items: I) -> Self

std-iter.collect.generic-owned-cursorFromIterator[T].from_iter[I < Iterator[T]](items: I) -> Self builds a collection from the owned cursor.
std-iter.prelude.from-iteratorstd.iter also declares FromIterator, which is not a prelude name. Code imports it to implement or name it, as in use std.iter.FromIterator, and a collect call needs no import.
std-iter.collect.callcollect returns C::from_iter(self).
std-iter.collect.expectedC is solved like any call-site type argument: from the expected type, or from an explicit list such as collect::[Map[string, i32]]().
std-iter.collect.defaultWhen nothing determines C, its declared default List[T] applies.
std-iter.collect.boundA C that does not implement FromIterator[T] is an error. Error: unsatisfied-trait-bound.

The standard library implements FromIterator for these prelude types:

Rule	Collection	Items	Result
std-iter.collect.listList	`List[T]`	`T`	every remaining item, in order
std-iter.collect.map-lastMap	`Map[K, V]`	`(K, V)`	one entry per pair; for an equal key the later value wins
std-iter.collect.resultAll results	`Result[C, E]`, where `C < FromIterator[T]`	`Result[T, E]`	`.Ok` of the `C` collected from the `.Ok` payloads, or the first `.Err`
std-iter.collect.optionAll values	`C?`, where `C < FromIterator[T]`	`T?`	`.Some` of the `C` collected from the `.Some` payloads, or `.None` at the first `.None`

std-iter.collect.owned-drainCollecting into a List or a Map advances self until next returns .None, which exhausts the owned cursor.
std-iter.collect.owned-stopCollecting into a Result or an optional stops at the first .Err or .None and leaves the rest of the owned cursor unread.
std-iter.collect.map-keyA Map collection needs K < Eq & Hash, as every map does.

Error example

fn total(values: List[i32]) -> i32:
    let size: i32 = values.iter().collect()  # error: unsatisfied-trait-bound
    size

Why. The expected type already names the target, as Rust's collect does. A Map built by collect agrees with a map literal and a map comprehension on equal keys.

Note. The standard library writes both of its Map implementations with that bound, as impl[K < Eq & Hash, V] FromIterator[(K, V)] for Map[K, V] and impl[K < Eq & Hash, V] Iterable[(K, V)] for Map[K, V]. Neither leaves the key unbounded.

#List And Optional Map

std also gives List[T] and T? a map method:

Receiver	Method
`List[T]`	`map[U](self, transform: fn(T) -> U) -> List[U]`
`T?`	`map[U](self, transform: fn(T) -> U) -> U?`

std-iter.method.mapList.map and optional map are non-suspending and evaluate the transform in source order.

tests:
    use std.testing.assert_equal

    it("map doubles each item, in order"):
        assert_equal([+3, 1, 2].map(fn(value: i32) -> i32: value * 2), [+6, 2, 4], reason="doubled")

    it("optional map keeps .None"):
        let absent: i32? = .None
        assert_equal(absent.map(fn(value: i32) -> i32: value * 2), .None, reason="kept")

See also: Built-In Methods, which lists the methods of the built-in types that stay in the language tier.