iyi

Standard library, 0.18.0

std/iterator

Iterator: lazy sequences.

import std/iterator to use it. Source: src/std/iterator.iyi at v0.18.0.

A pull-based sequence abstraction that makes transformations composable without allocating an intermediate array at each stage. Against the Go bar, which has no lazy sequence abstraction, this gives iyi expressive power while avoiding needless heap allocations.

## The Associated Type and Lazy Adaptors

Like Enumerable, Iterator uses an associated type type Elem. The core requirement is a single method:

  abstract def next : Elem | Stop

Answering Stop signals exhaustion. It is no value of any element type, so a nil element is an element: with next : Elem? the end was nil, and Iterator.of([1, nil, 3]).to_a stopped at the nil and answered [1], where the other library, whose next answers its Iterator::Stop in the same place, answers [1, nil, 3]. Stop holds nothing, so answering it allocates nothing.

### Why adaptors take (I, T, U) rather than (I, U)

In a naive design, MapIterator would be parameterized as (I, U) with @func : I::Elem -> U. However, when I is an unspecialized type variable on a struct definition, the compiler projects I::Elem against the generic declaration rather than specializing it to the receiver's type arguments. For example, ArrayIterator(Int32)::Elem resolves to the unspecialized T rather than Int32, causing the constructor to expect Proc(T, U) instead of Proc(Int32, U).

Passing Elem explicitly as a type parameter T solves this completely:

  def map(&func : Elem -> U) : MapIterator(self, Elem, U) forall U
    MapIterator(self, Elem, U).new(self, func)
  end

Inside Iterator#map, self is the concrete implementer and Elem is its known associated type. Passing Elem directly into MapIterator(self, Elem, U) avoids inter-struct projection, produces zero heap overhead, and maintains full static type safety.

## Why Enumerable does not have #lazy

Enumerable defines abstract def each(& : Elem -> Nil) : Nil. A push-based interface cannot be converted to a pull-based iterator without either: 1. Buffering the entire sequence into an array, which destroys laziness and

 hangs on infinite sequences, or

2. Stackful coroutines or fibers, which are absent from the minimal runtime. Concrete collections provide their own iterator constructors instead: Iterator.of(array), Iterator.of(range), Iterator.of_keys(hash), Iterator.of_values(hash), Iterator.of_entries(hash). That avoids any circular dependency between std/enumerable and std/iterator, and keeps one spelling per source: the prelude types are not reopened to add a second.

## What is refused

take/skip refuse a negative count (negative count: -1), each_slice, each_cons and step refuse a non-positive size, all at the call that built the adaptor rather than from inside the struct that ran it. first, max and min panic on an exhausted source with the Enumerable sentences (first of an empty collection); first?, max? and min? answer nil. find answers nil, as Array#find and Enumerable#find do.

## What is not here and why

  • N-ary zip(*others): one binary zip(other : O) with O::Elem, composable into multiple zips if needed.
  • cons_pair: redundant with each_cons(2).
  • in_slices_of, chunks: require structural constraints on tuples or pairs.

ArrayIterator(T)class

The sources are classes, as the other library's are: an adaptor keeps its source by value, and a struct source was copied into it, so it.first(2).to_a and then it.to_a gave [1, 2] and [1, 2, 3, 4] where the other library gives [1, 2] and [3, 4]. Shared, the adaptor's pulls are the source's. An adaptor that keeps a count, a flag or a buffer is the source of whatever is built on it, so it is a class for the same reason: as a struct it was copied too, and t = it.take(3), t.first(2).to_a and then t.to_a gave [3, 4, 5] where the other library gives [3], each_cons handed its first window out again and step and with_index restarted their strides and counts. An adaptor that keeps only its sources, a block or a size stays a struct: a copy of it pulls from the same place.

Each type defines next once and its impl names only Elem, as NumericStepIterator (std/steppable) does: every adaptor carried the same next twice, once on the type and once in the impl.

std/iteratoriyi doc src/std/iterator.iyi
pub class ArrayIterator(T)
  def initialize(array : Array(T))
  def next : T | Stop
end

ChainIterator(I1, I2, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class ChainIterator(I1, I2, T)
  def initialize(iter1 : I1, iter2 : I2)
  def next : T | Stop
end

CompactMapIterator(I, T, U)struct

std/iteratoriyi doc src/std/iterator.iyi
pub struct CompactMapIterator(I, T, U)
  def initialize(iter : I, func : (T -> U | ::Nil))
  def next : U | Stop
end

ConsIterator(I, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class ConsIterator(I, T)
  def initialize(iter : I, n : Int32)
  def next : Array(T) | Stop
end

CycleIterator(I, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class CycleIterator(I, T)
  def initialize(iter : I)
  def next : T | Stop
end

CycleNIterator(I, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class CycleNIterator(I, T)
  def initialize(iter : I, n : Int32)
  def next : T | Stop
end

EndlessRangeIterator(B)class

The source an endless range gets: it counts up by one from the beginning with no end, as an endless range does in the other library.

std/iteratoriyi doc src/std/iterator.iyi
pub class EndlessRangeIterator(B)
  def initialize(current : B)
  def next : B
end

EntryIterator(K, V)class

std/iteratoriyi doc src/std/iterator.iyi
pub class EntryIterator(K, V)
  def initialize(hash : Hash(K, V))
  def next : Tuple(K, V) | Stop
end

FlatMapIterator(I, T, U)class

std/iteratoriyi doc src/std/iterator.iyi
pub class FlatMapIterator(I, T, U)
  def initialize(iter : I, func : (T -> Array(U)))
  def next : U | Stop
end

Iteratortrait

std/iteratoriyi doc src/std/iterator.iyi
pub trait Iterator
  type Elem
  def all?(& : (Elem -> Bool)) : Bool
  # Whether an element is truthy, which is what the other library's `any?`
  # answers: this said whether there was an element at all, so
  # `Iterator.of([false, false]).any?` was true. It pulls until it meets a
  # truthy element, and what it pulled is gone: an iterator is a pull, so a
  # predicate over one cannot be free. For a source with no `false` in it
  # that is one element. The block form below reads as much as it has to
  # and no more. Said here because a method spelled like a question that
  # quietly takes elements is the kind of thing a caller finds out from the
  # answer to the *next* question.
  def any? : Bool
  def any?(& : (Elem -> Bool)) : Bool
  def chain(other : O) : ChainIterator(self, O, Elem | O::Elem) forall O : Iterator
  def compact_map(&func : (Elem -> U | ::Nil)) : CompactMapIterator(self, Elem, U) forall U
  def count : Int32
  def count(& : (Elem -> Bool)) : Int32
  def cycle(n : Int32) : CycleNIterator(self, Elem)
  def cycle : CycleIterator(self, Elem)
  def each(& : (Elem -> Nil)) : Nil
  def each_cons(n : Int32) : ConsIterator(self, Elem)
  def each_slice(n : Int32) : SliceIterator(self, Elem)
  # Nil when nothing matched, which is what `Enumerable#find` and `Array#find`
  # answer: not finding is the ordinary outcome of a search, and a caller who
  # wants the panic writes `|| raise` as the prelude does. `first?`/`first`
  # below keeps its pair — an exhausted iterator has no first element, which
  # is a question with no answer.
  def find(& : (Elem -> Bool)) : Elem | ::Nil
  def first(n : Int32) : TakeIterator(self, Elem)
  def first : Elem
  def first? : Elem | ::Nil
  def flat_map(&func : (Elem -> Array(U))) : FlatMapIterator(self, Elem, U) forall U
  def map(&func : (Elem -> U)) : MapIterator(self, Elem, U) forall U
  def max : Elem where Elem : Comparable
  # The largest, or nil when there is none. `max?`/`max` is a real pair:
  # an empty source has no largest element, so the plain name raising is
  # the common case. This file keeps the same pair for `first?`/`first`,
  # and answers `find` with nil, where not finding is the ordinary outcome.
  def max? : Elem | ::Nil where Elem : Comparable
  def min : Elem where Elem : Comparable
  # And the same pair at the other end.
  def min? : Elem | ::Nil where Elem : Comparable
  abstract def next : Elem | Stop
  def none?(& : (Elem -> Bool)) : Bool
  # Convenience constructor for arrays.
  def self.of(array : Array(T)) : ArrayIterator(T) forall T
  # An endless range counts up for as long as it is pulled, as the other
  # library's does: `Iterator.of((1..)).first(3).to_a` was accepted here
  # and then refused from inside `RangeIterator#next`, "expected argument
  # #1 to 'Int32#<' to be ... not Nil", a line of this file. A beginless
  # range has no first element to count from, and is refused at the call.
  def self.of(range : Range(B, Nil)) : EndlessRangeIterator(B) forall B
  def self.of(range : Range(Nil, E)) : Nil forall E
  def self.of(range : Range(B, E)) : RangeIterator(B, E) forall B, E
  def self.of_entries(hash : Hash(K, V)) : EntryIterator(K, V) forall K, V
  def self.of_keys(hash : Hash(K, V)) : KeyIterator(K, V) forall K, V
  def self.of_values(hash : Hash(K, V)) : ValueIterator(K, V) forall K, V
  def product : Elem where Elem : Num
  def reduce(initial : U, & : (U, Elem -> U)) : U forall U
  def reduce?(& : (Elem, Elem -> Elem)) : Elem | ::Nil
  def reject(&func : (Elem -> Bool)) : RejectIterator(self, Elem)
  def select(&func : (Elem -> Bool)) : SelectIterator(self, Elem)
  def size : Int32
  def skip(n : Int32) : SkipIterator(self, Elem)
  def skip_while(&func : (Elem -> Bool)) : SkipWhileIterator(self, Elem)
  def step(n : Int32) : StepIterator(self, Elem)
  def sum : Elem where Elem : Num
  def take(n : Int32) : TakeIterator(self, Elem)
  def take_while(&func : (Elem -> Bool)) : TakeWhileIterator(self, Elem)
  def to_a : Array(Elem)
  def with_index(offset : Int32 = 0) : WithIndexIterator(self, Elem)
  def with_index(offset : Int32 = 0, & : (Elem, Int32 -> Nil)) : Nil
  # Bounded, as `Enumerable#zip` is (SPEC.md II.6 finding 6). Unbounded, a
  # zip with an array was refused from inside this file, "undefined
  # constant O::Elem" at the line below, and a chain with one from
  # `ChainIterator#next`; with `forall O : Iterator` the refusal names the
  # caller's line, the argument's type and `O`. A chain of two element
  # types yields either, as the other library's does: it was a return-type
  # error inside `ChainIterator`.
  def zip(other : O) : ZipIterator(self, Elem, O, O::Elem) forall O : Iterator
end

KeyIterator(K, V)class

The three views of a hash, in insertion order. Each takes its snapshot of the hash once, when built — Hash#keys and Hash#values allocate a fresh array per call, so asking per element was a copy of the table per step — and then walks that snapshot, so a hash that changes under the iterator does not change what it yields.

std/iteratoriyi doc src/std/iterator.iyi
pub class KeyIterator(K, V)
  def initialize(hash : Hash(K, V))
  def next : K | Stop
end

MapIterator(I, T, U)struct

std/iteratoriyi doc src/std/iterator.iyi
pub struct MapIterator(I, T, U)
  def initialize(iter : I, func : (T -> U))
  def next : U | Stop
end

RangeIterator(B, E)class

Counts up by one from the range's beginning, the way the prelude's Range#each does, and stops at the end rather than stepping past it: on an inclusive range whose end is the type's largest value, the step after the last element would overflow.

std/iteratoriyi doc src/std/iterator.iyi
pub class RangeIterator(B, E)
  def initialize(range : Range(B, E))
  def next : B | Stop
end

RejectIterator(I, T)struct

std/iteratoriyi doc src/std/iterator.iyi
pub struct RejectIterator(I, T)
  def initialize(iter : I, func : (T -> Bool))
  def next : T | Stop
end

SelectIterator(I, T)struct

std/iteratoriyi doc src/std/iterator.iyi
pub struct SelectIterator(I, T)
  def initialize(iter : I, func : (T -> Bool))
  def next : T | Stop
end

SkipIterator(I, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class SkipIterator(I, T)
  def initialize(iter : I, n : Int32)
  def next : T | Stop
end

SkipWhileIterator(I, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class SkipWhileIterator(I, T)
  def initialize(iter : I, func : (T -> Bool))
  def next : T | Stop
end

SliceIterator(I, T)struct

std/iteratoriyi doc src/std/iterator.iyi
pub struct SliceIterator(I, T)
  def initialize(iter : I, n : Int32)
  def next : Array(T) | Stop
end

StepIterator(I, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class StepIterator(I, T)
  def initialize(iter : I, by : Int32)
  def next : T | Stop
end

Stopstruct

std/iteratoriyi doc src/std/iterator.iyi
pub struct Stop
  def initialize
end

TakeIterator(I, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class TakeIterator(I, T)
  def initialize(iter : I, n : Int32)
  def next : T | Stop
end

TakeWhileIterator(I, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class TakeWhileIterator(I, T)
  def initialize(iter : I, func : (T -> Bool))
  def next : T | Stop
end

ValueIterator(K, V)class

std/iteratoriyi doc src/std/iterator.iyi
pub class ValueIterator(K, V)
  def initialize(hash : Hash(K, V))
  def next : V | Stop
end

WithIndexIterator(I, T)class

std/iteratoriyi doc src/std/iterator.iyi
pub class WithIndexIterator(I, T)
  def initialize(iter : I, offset : Int32)
  def next : Tuple(T, Int32) | Stop
end

ZipIterator(I1, T1, I2, T2)struct

std/iteratoriyi doc src/std/iterator.iyi
pub struct ZipIterator(I1, T1, I2, T2)
  def initialize(iter1 : I1, iter2 : I2)
  # Asks the second source only when the first has an element. Asking both
  # took one from the second each time the first had run out: after
  # `a.zip(b).to_a` with `a` = [1] and `b` = [10, 20, 30], `b.next`
  # answered 30 where the other library and Python's `zip` answer 20.
  def next : Tuple(T1, T2) | Stop
end

Iterator for EndlessRangeIterator(B) forall Bimpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for EndlessRangeIterator(B) forall B
end

Iterator for ArrayIterator(T) forall Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for ArrayIterator(T) forall T
end

Iterator for RangeIterator(B, E) forall B, Eimpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for RangeIterator(B, E) forall B, E
end

Iterator for KeyIterator(K, V) forall K, Vimpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for KeyIterator(K, V) forall K, V
end

Iterator for ValueIterator(K, V) forall K, Vimpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for ValueIterator(K, V) forall K, V
end

Iterator for EntryIterator(K, V) forall K, Vimpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for EntryIterator(K, V) forall K, V
end

Iterator for MapIterator(I, T, U) forall I, T, Uimpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for MapIterator(I, T, U) forall I, T, U
end

Iterator for SelectIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for SelectIterator(I, T) forall I, T
end

Iterator for RejectIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for RejectIterator(I, T) forall I, T
end

Iterator for TakeIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for TakeIterator(I, T) forall I, T
end

Iterator for TakeWhileIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for TakeWhileIterator(I, T) forall I, T
end

Iterator for SkipIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for SkipIterator(I, T) forall I, T
end

Iterator for SkipWhileIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for SkipWhileIterator(I, T) forall I, T
end

Iterator for ZipIterator(I1, T1, I2, T2) forall I1, T1, I2, T2impl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for ZipIterator(I1, T1, I2, T2) forall I1, T1, I2, T2
end

Iterator for ChainIterator(I1, I2, T) forall I1, I2, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for ChainIterator(I1, I2, T) forall I1, I2, T
end

Iterator for FlatMapIterator(I, T, U) forall I, T, Uimpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for FlatMapIterator(I, T, U) forall I, T, U
end

Iterator for SliceIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for SliceIterator(I, T) forall I, T
end

Iterator for ConsIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for ConsIterator(I, T) forall I, T
end

Iterator for WithIndexIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for WithIndexIterator(I, T) forall I, T
end

Iterator for CycleIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for CycleIterator(I, T) forall I, T
end

Iterator for CycleNIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for CycleNIterator(I, T) forall I, T
end

Iterator for StepIterator(I, T) forall I, Timpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for StepIterator(I, T) forall I, T
end

Iterator for CompactMapIterator(I, T, U) forall I, T, Uimpl

std/iteratoriyi doc src/std/iterator.iyi
impl Iterator for CompactMapIterator(I, T, U) forall I, T, U
end