for value in source is built on two prelude traits. Iterable[T] says “you
can ask me for a cursor”; Iterator[T] is the cursor itself, and yields
Option[T] until it runs out.
fn main(): void {
names := ["ada", "grace", "alan"]
for name in names {
println(name)
}
}That loop desugars to names.iterator() followed by repeated next() calls
until one returns None. Anything implementing either trait can appear on the
right of in — lists, strings, maps, sets, slices, ranges, streams, and your
own types.
for is the only loop construct in Atoll. This page covers the iteration
protocol and the operators that compose over it; the four for forms
(for pat in x, for cond, for pat := expr, and bare for { }) are
specified in Loops.
The two traits
Iterator[T] has one required method:
trait Iterator[T] {
fn next(mut self): Option[T]
}Iterable[T] has an associated type and one required method:
trait Iterable[T] {
type Iter: Iterator[T]
fn iterator(self): Iter
}The split matters. An Iterable is a source and can be traversed many times,
because each iterator() call hands back a fresh cursor. An Iterator is a
position and is consumed as it advances.
fn main(): void {
values := [1, 2, 3]
// `values` is Iterable — traversing it twice is fine.
for v in values { println("first pass ${v}") }
for v in values { println("second pass ${v}") }
// A cursor is used up. The second `count()` sees an exhausted iterator.
mut cursor := values.iterator()
println("${cursor.count()}") // 3
println("${cursor.count()}") // 0 — nothing left
}Driving a cursor by hand
next() is the whole protocol. Everything else is built on it, and writing the
loop out is always available:
fn main(): void {
readings := [12, 7, 40, 3, 25]
mut cursor := readings.iterator()
mut total := 0
mut done := false
for !done {
match cursor.next() {
Some(v) => { total = total + v }
None => { done = true }
}
}
println("total ${total}")
}for v in cursor is the same loop with the match written for you, and works
on a cursor as well as on a collection:
fn main(): void {
readings := [12, 7, 40, 3, 25]
mut cursor := readings.iterator()
for v in cursor {
println("${v}")
}
}Consuming a builtin cursor
Iterator supplies default methods on top of next. On the prelude’s own
cursors — ListIter, SetIter, MapKeysIter, and friends — these lower and
run today.
| Method | Consumption |
|---|---|
count() |
Counts and exhausts the remainder |
first() |
Pulls at most one element |
last() |
Exhausts and returns the final element |
any(f) / all(f) |
Stop as soon as the answer is decided |
find(f) |
Stops at the first match |
fn main(): void {
readings := [12, 7, 40, 3, 25]
mut a := readings.iterator()
println("any over 30? ${a.any(v => v > 30)}")
mut b := readings.iterator()
println("all positive? ${b.all(v => v > 0)}")
mut c := readings.iterator()
println("first over 20: ${c.find(v => v > 20) ?? -1}")
mut d := readings.iterator()
println("head ${d.first() ?? -1}")
mut e := readings.iterator()
println("tail ${e.last() ?? -1}")
}Each of those takes a fresh iterator() because the previous one has been
consumed. After a short-circuiting call the cursor sits just past the element
that decided the answer — it is not rewound.
Iterator also declares for_each(f). It is real, but a non-capturing
callback currently fails to lower with an internal error (ATOLL5001), so
prefer for v in cursor, which has no such limitation.
Lazy adapters are not usable yet
Iterator declares four chainable adapters — map(f), filter(f), take(n),
and skip(n) — that wrap one cursor in another without visiting anything.
Their wrapper types (MapIter, FilterIter, TakeIter, SkipIter) are
declared in the prelude, but a monomorphized wrapper does not satisfy
Iterator, so no program that calls one can be compiled. atoll check
accepts the chain; atoll build rejects it:
fn main(): void {
readings := [12, 7, 40, 3, 25, 61, 8]
// Type-checks, then fails to lower:
// ATOLL3100: type `ListIter[int]` does not implement trait `Iterator`
mut pipeline := readings.iterator().filter(v => v > 10).take(2)
for v in pipeline { println("${v}") }
}Until that is fixed, compose with the eager list operators instead. They allocate an intermediate list at each step, and they work:
fn main(): void {
readings := [12, 7, 40, 3, 25, 61, 8]
loud := readings
.filter(v => v > 10)
.map(v => v * 2)
.take(2)
for v in loud { println("${v}") }
println("${loud.len()} kept")
}filter, map, take, skip, take_while, skip_while, flat_map,
distinct, partition, scan, fold, sorted, enumerate, and reversed
all lower on []T; see Sequences for the full
surface. When the source is long and you only want a prefix, put take first
so the later stages see fewer elements.
Implementing Iterator
Implement next on a struct that holds the traversal state. The struct is the
cursor, so next takes mut self.
struct Countdown { remaining: int }
impl Iterator[int] for Countdown {
fn next(mut self): Option[int] {
if self.remaining <= 0 { return None }
self.remaining = self.remaining - 1
return Some(self.remaining)
}
}
fn main(): void {
mut c := Countdown { remaining: 5 }
for v in c {
println("${v}")
}
// The same traversal without the loop sugar.
mut d := Countdown { remaining: 3 }
mut done := false
for !done {
match d.next() {
Some(v) => println("manual ${v}")
None => { done = true }
}
}
}An iterator does not have to be finite — next may never return None. Bound
it where you consume it:
struct Fib { a: int, b: int }
impl Iterator[int] for Fib {
fn next(mut self): Option[int] {
current := self.a
self.a = self.b
self.b = current + self.b
return Some(current) // never None
}
}
fn main(): void {
mut f := Fib { a: 0, b: 1 }
mut taken: []int = []
mut done := false
for !done {
if taken.len() >= 10 {
done = true
} else {
match f.next() {
Some(v) => { taken.add(v) }
None => { done = true }
}
}
}
for v in taken { println("${v}") }
}The Iterator default methods (count, find, any, last, …) are declared
for every implementor, but on a user type they do not survive
monomorphization: calling c.count() on a Countdown type-checks and then
fails to build with ATOLL3100. Write the loop, as above, or collect into a
[]T first.
Implementing Iterable
Pair the cursor with a collection type that knows how to build one. The
associated type Iter names the cursor struct.
struct RingIter { values: []int, at: int, remaining: int, start: int }
impl Iterator[int] for RingIter {
fn next(mut self): Option[int] {
if self.remaining <= 0 { return None }
slot := (self.start + self.at) % self.values.len()
self.at = self.at + 1
self.remaining = self.remaining - 1
return self.values.get(slot.to_u32())
}
}
struct Ring { values: []int, start: int }
impl Iterable[int] for Ring {
type Iter = RingIter
fn iterator(self): RingIter {
return RingIter {
values: self.values,
at: 0,
remaining: self.values.len(),
start: self.start,
}
}
}
fn main(): void {
ring := Ring { values: [10, 20, 30, 40], start: 2 }
// A fresh cursor per traversal, so the ring can be walked repeatedly.
for v in ring { println("${v}") }
for v in ring { println("again ${v}") }
}The rule to follow: iterator() must construct progress state, never hand
out a cursor that the collection itself keeps mutating. Returning a shared
cursor makes the second traversal silently empty.
Iterable also declares three eager defaults — for_each_item(f),
count_items(), and first_item(). As with the Iterator defaults, they are
not available to user types yet: ring.count_items() type-checks and then
fails to build. A for loop over the source does the same job, and takes its
own fresh cursor each time:
struct RingIter { values: []int, at: int }
impl Iterator[int] for RingIter {
fn next(mut self): Option[int] {
if self.at >= self.values.len() { return None }
v := self.values.get(self.at.to_u32())
self.at = self.at + 1
return v
}
}
struct Ring { values: []int }
impl Iterable[int] for Ring {
type Iter = RingIter
fn iterator(self): RingIter { return RingIter { values: self.values, at: 0 } }
}
fn count_of(ring: Ring): int {
mut n := 0
for _ in ring { n = n + 1 }
return n
}
fn main(): void {
ring := Ring { values: [1, 2, 3] }
println("${count_of(ring)}")
println("${count_of(ring)}") // still 3 — nothing was consumed
}Writing generic code
Take I: Iterable[T] when the function traverses a source, and I: Iterator[T]
when it drives a cursor it is allowed to consume.
struct Countdown { remaining: int }
impl Iterator[int] for Countdown {
fn next(mut self): Option[int] {
if self.remaining <= 0 { return None }
self.remaining = self.remaining - 1
return Some(self.remaining)
}
}
struct Ring { values: []int }
impl Iterable[int] for Ring {
type Iter = Countdown
fn iterator(self): Countdown { return Countdown { remaining: self.values.len() } }
}
fn total[I: Iterable[int]](source: I): int {
mut sum := 0
for v in source { sum = sum + v }
return sum
}
fn drain[I: Iterator[int]](mut cursor: I): int {
mut sum := 0
mut done := false
for !done {
match cursor.next() {
Some(v) => { sum = sum + v }
None => { done = true }
}
}
return sum
}
fn main(): void {
println("${total(Ring { values: [1, 2, 3, 4] })}")
println("${drain(Countdown { remaining: 4 })}")
}One sharp edge: those bounds resolve for user types, but a builtin
container passed at an Iterable/Iterator bound currently fails
monomorphization (type List[?2] does not implement trait Iterable). Take a
concrete []T or [..]T parameter when the caller will pass a prelude
collection:
fn total(values: []int): int {
mut sum := 0
for v in values { sum = sum + v }
return sum
}
fn main(): void {
println("${total([1, 2, 3, 4])}")
}That is usually the better signature anyway: []T also gives the algorithm a
length and indices, which Iterable does not.
Sources in the prelude
Every builtin container is iterable, and each yields a different element shape.
fn main(): void {
// List: elements.
for v in [1, 2, 3] { println("${v}") }
// String: characters.
for ch in "abc" { println("${ch}") }
// Range: half-open, then inclusive.
for i in 0..3 { println("${i}") }
for i in 0..=3 { println("${i}") }
// Set: members, in unspecified order.
mut tags: Set[string] = Set.new()
tags.add("x")
for tag in tags { println(tag) }
// Map: (K, V) entries, destructured by the loop pattern.
mut ports: Map[string, int] = Map.new()
ports.put("http", 80)
for name, port in ports { println("${name} ${port}") }
}Indexed traversal is available where positions exist, and enumerate() pairs
each element with its index:
fn main(): void {
values := [10, 20, 30]
for index, value in values.enumerate() {
println("${index}: ${value}")
}
for index in 0..values.len() {
println("${values.get(index.to_u32()) ?? 0}")
}
for value in values.reversed() {
println("${value}")
}
}Prefer direct iteration; reach for an index range only when the index is part of the computation.
A slice is iterable too, and iterating it borrows rather than copies:
fn main(): void {
values := [1, 2, 3, 4, 5]
match values.slice(1..4) {
Some(window) => {
for v in window { println("${v}") }
}
None => println("out of range")
}
}A Stream is drained with the
pattern-consume form rather than for … in:
fn main(): void {
s := Stream.new[int](4)
s.send(1)
s.send(2)
s.close()
for Some(value) := s.recv() {
println("${value}")
}
}A worked example
A log scanner: a custom cursor over records, an Iterable wrapper so the log
can be walked more than once, and two consumers — one that stops early, one
that visits everything.
struct Record { level: string, message: string }
struct RecordIter { source: []Record, at: int }
impl Iterator[Record] for RecordIter {
fn next(mut self): Option[Record] {
if self.at >= self.source.len() { return None }
item := self.source.get(self.at.to_u32())
self.at = self.at + 1
return item
}
}
struct Log { records: []Record }
impl Iterable[Record] for Log {
type Iter = RecordIter
fn iterator(self): RecordIter { return RecordIter { source: self.records, at: 0 } }
}
// Stops pulling as soon as `limit` matches are in hand — the tail of the
// log is never touched.
fn first_errors(log: Log, limit: int): []string {
mut out: []string = []
mut cursor := log.iterator()
mut done := false
for !done {
if out.len() >= limit {
done = true
} else {
match cursor.next() {
None => { done = true }
Some(r) => {
if r.level == "error" { out.add(r.message) }
}
}
}
}
return out
}
// Takes its own fresh cursor via the `Iterable` impl.
fn counts_by_level(log: Log): Map[string, int] {
mut counts: Map[string, int] = Map.new()
for record in log {
counts.put(record.level, counts.get_or_default(record.level, 0) + 1)
}
return counts
}
fn main(): void {
log := Log {
records: [
Record { level: "info", message: "listening" },
Record { level: "error", message: "connect refused" },
Record { level: "warn", message: "slow query" },
Record { level: "error", message: "timeout" },
Record { level: "error", message: "disk full" },
],
}
for message in first_errors(log, 2) {
println("error: ${message}")
}
counts := counts_by_level(log)
for level in counts.keys().to_list().sorted() {
println("${level}: ${counts.get_or_default(level, 0)}")
}
}Both functions run against the same Log value, because each one asks the
Iterable for its own cursor rather than sharing one.