Iter

type Iter<T> = Types.Iter<T>

An iterator that produces values of type T. Calling next returns null when iteration is finished.

Iterators are inherently stateful. Calling next "consumes" a value from the Iterator that cannot be put back, so keep that in mind when sharing iterators between consumers.

An iterator i can be iterated over using

for (x in i) {
  …do something with x…
}

public func empty<T>() : Iter<T>

Creates an empty iterator.

import Iter "mo:new-base/Iter";
for (x in Iter.empty<Nat>())
  assert false; // This loop body will never run

public func singleton<T>(value : T) : Iter<T>

Creates an iterator that produces a single value.

import Iter "mo:new-base/Iter";
var sum = 0;
for (x in Iter.singleton(3))
  sum += x;
assert(3 == sum);

public func forEach<T>(iter : Iter<T>, f : (T) -> ())

Calls a function f on every value produced by an iterator and discards the results. If you're looking to keep these results use map instead.

import Iter "mo:new-base/Iter";
var sum = 0;
Iter.forEach<Nat>([1, 2, 3].values(), func(x) {
  sum += x;
});
assert(6 == sum)

public func enumerate<T>(iter : Iter<T>) : Iter<(Nat, T)>

Takes an iterator and returns a new iterator that pairs each element with its index. The index starts at 0 and increments by 1 for each element.

import Iter "mo:new-base/Iter";
let iter = Iter.fromArray(["A", "B", "C"]);
let enumerated = Iter.enumerate(iter);
Array.toArray(enumerated) // => [(0, "A"), (1, "B"), (2, "C")];

public func step<T>(iter : Iter<T>, n : Nat) : Iter<T>

Creates a new iterator that yields every nth element from the original iterator. If interval is 0, returns an empty iterator. If interval is 1, returns the original iterator. For any other positive interval, returns an iterator that skips interval - 1 elements after each yielded element.

import Iter "mo:new-base/Iter";
let iter = Iter.fromArray([1, 2, 3, 4, 5, 6]);
let steppedIter = Iter.step(iter, 2); // Take every 2nd element
assert(?1 == steppedIter.next());
assert(?3 == steppedIter.next());
assert(?5 == steppedIter.next());
assert(null == steppedIter.next());

public func size<T>(iter : Iter<T>) : Nat

Consumes an iterator and counts how many elements were produced (discarding them in the process).

import Iter "mo:new-base/Iter";
let iter = [1, 2, 3].values();
assert(3 == Iter.size(iter));

public func map<T, R>(iter : Iter<T>, f : T -> R) : Iter<R>

Takes a function and an iterator and returns a new iterator that lazily applies the function to every element produced by the argument iterator.

import Iter "mo:new-base/Iter";
let iter = [1, 2, 3].values();
let mappedIter = Iter.map<Nat, Nat>(iter, func (x) = x * 2);
Iter.toArray(mappedIter) // => [2, 4, 6]

public func filter<T>(iter : Iter<T>, f : T -> Bool) : Iter<T>

Creates a new iterator that only includes elements from the original iterator for which the predicate function returns true.

import Iter "mo:new-base/Iter";
let iter = [1, 2, 3, 4, 5].values();
let evenNumbers = Iter.filter<Nat>(iter, func (x) = x % 2 == 0);
Iter.toArray(evenNumbers) // => [2, 4]

public func filterMap<T, R>(iter : Iter<T>, f : T -> ?R) : Iter<R>

Creates a new iterator by applying a transformation function to each element of the original iterator. Elements for which the function returns null are excluded from the result.

import Iter "mo:new-base/Iter";
let iter = [1, 2, 3].values();
let evenNumbers = Iter.filterMap<Nat, Nat>(iter, func (x) = if (x % 2 == 0) ?x else null);
Iter.toArray(evenNumbers) // => [2]

public func flatten<T>(iter : Iter<Iter<T>>) : Iter<T>

Flattens an iterator of iterators into a single iterator by concatenating the inner iterators.

Possible optimization: Use flatMap when you need to transform elements before calling flatten. Example: use flatMap(...) instead of flatten(map(...)).

import Iter "mo:new-base/Iter";
let iter = Iter.flatten([[1, 2].values(), [3].values(), [4, 5, 6].values()].values());
Iter.toArray(iter) // => [1, 2, 3, 4, 5, 6]

public func flatMap<T, R>(iter : Iter<T>, f : T -> Iter<R>) : Iter<R>

Transforms every element of an iterator into an iterator and concatenates the results.

import Iter "mo:new-base/Iter";
let iter = Iter.flatMap<Nat, Nat>([1, 3, 5].values(), func (x) = [x, x + 1].values());
Iter.toArray(iter) // => [1, 2, 3, 4, 5, 6]

public func take<T>(iter : Iter<T>, n : Nat) : Iter<T>

Returns a new iterator that yields at most, first n elements from the original iterator. After n elements have been produced or the original iterator is exhausted, subsequent calls to next() will return null.

import Iter "mo:new-base/Iter";
let iter = Iter.fromArray([1, 2, 3, 4, 5]);
let first3 = Iter.take(iter, 3);
Iter.toArray(first3) // => [1, 2, 3]

import Iter "mo:new-base/Iter";
let iter = Iter.fromArray([1, 2, 3]);
let first5 = Iter.take(iter, 5);
Iter.toArray(first5) // => [1, 2, 3] only 3 elements in the original iterator

public func takeWhile<T>(iter : Iter<T>, f : T -> Bool) : Iter<T>

Returns a new iterator that yields elements from the original iterator until the predicate function returns false. The first element for which the predicate returns false is not included in the result.

import Iter "mo:new-base/Iter";
let iter = Iter.fromArray([1, 2, 3, 4, 5, 4, 3, 2, 1]);
let result = Iter.takeWhile<Nat>(iter, func (x) = x < 4);
Iter.toArray(result) // => [1, 2, 3] note the difference between `takeWhile` and `filter`

public func drop<T>(iter : Iter<T>, n : Nat) : Iter<T>

Returns a new iterator that skips the first n elements from the original iterator. If the original iterator has fewer than n elements, the result will be an empty iterator.

import Iter "mo:new-base/Iter";
let iter = Iter.fromArray([1, 2, 3, 4, 5]);
let skipped = Iter.drop(iter, 3);
Iter.toArray(skipped) // => [4, 5]

public func dropWhile<T>(iter : Iter<T>, f : T -> Bool) : Iter<T>

Returns a new iterator that skips elements from the original iterator until the predicate function returns false. The first element for which the predicate returns false is the first element produced by the new iterator.

import Iter "mo:new-base/Iter";
let iter = Iter.fromArray([1, 2, 3, 4, 5, 4, 3, 2, 1]);
let result = Iter.dropWhile<Nat>(iter, func (x) = x < 4);
Iter.toArray(result) // => [4, 5, 4, 3, 2, 1] notice that `takeWhile` and `dropWhile` are complementary

public func zip<A, B>(a : Iter<A>, b : Iter<B>) : Iter<(A, B)>

Zips two iterators into a single iterator that produces pairs of elements. The resulting iterator will stop producing elements when either of the input iterators is exhausted.

import Iter "mo:new-base/Iter";
let iter1 = [1, 2, 3].values();
let iter2 = ["A", "B"].values();
let zipped = Iter.zip(iter1, iter2);
Iter.toArray(zipped) // => [(1, "A"), (2, "B")] note that the third element from iter1 is not included, because iter2 is exhausted

public func zip3<A, B, C>(
  a : Iter<A>,
  b : Iter<B>,
  c : Iter<C>
) : Iter<(A, B, C)>

Zips three iterators into a single iterator that produces triples of elements. The resulting iterator will stop producing elements when any of the input iterators is exhausted.

import Iter "mo:new-base/Iter";
let iter1 = ["A", "B"].values();
let iter2 = ["1", "2", "3"].values();
let iter3 = ["x", "y", "z", "xd"].values();
let zipped = Iter.zip3(iter1, iter2, iter3);
Iter.toArray(zipped) // => [("A", "1", "x"), ("B", "2", "y")] note that the unmatched elements from iter2 and iter3 are not included

public func zipWith<A, B, R>(
  a : Iter<A>,
  b : Iter<B>,
  f : (A, B) -> R
) : Iter<R>

Zips two iterators into a single iterator by applying a function to zipped pairs of elements. The resulting iterator will stop producing elements when either of the input iterators is exhausted.

import Iter "mo:new-base/Iter";
let iter1 = ["A", "B"].values();
let iter2 = ["1", "2", "3"].values();
let zipped = Iter.zipWith<Text, Text, Text>(iter1, iter2, func (a, b) = a # b);
Iter.toArray(zipped) // => ["A1", "B2"] note that the third element from iter2 is not included, because iter1 is exhausted

public func zipWith3<A, B, C, R>(
  a : Iter<A>,
  b : Iter<B>,
  c : Iter<C>,
  f : (A, B, C) -> R
) : Iter<R>

Zips three iterators into a single iterator by applying a function to zipped triples of elements. The resulting iterator will stop producing elements when any of the input iterators is exhausted.

import Iter "mo:new-base/Iter";
let iter1 = ["A", "B"].values();
let iter2 = ["1", "2", "3"].values();
let iter3 = ["x", "y", "z", "xd"].values();
let zipped = Iter.zipWith3<Text, Text, Text, Text>(iter1, iter2, iter3, func (a, b, c) = a # b # c);
Iter.toArray(zipped) // => ["A1x", "B2y"] note that the unmatched elements from iter2 and iter3 are not included

public func all<T>(iter : Iter<T>, f : T -> Bool) : Bool

Checks if a predicate function is true for all elements produced by an iterator. It stops consuming elements from the original iterator as soon as the predicate returns false.

import Iter "mo:new-base/Iter";
Iter.all<Nat>([1, 2, 3].values(), func (x) = x < 4) // => true
Iter.all<Nat>([1, 2, 3].values(), func (x) = x < 3) // => false

public func any<T>(iter : Iter<T>, f : T -> Bool) : Bool

Checks if a predicate function is true for any element produced by an iterator. It stops consuming elements from the original iterator as soon as the predicate returns true.

import Iter "mo:new-base/Iter";
Iter.any<Nat>([1, 2, 3].values(), func (x) = x == 2) // => true
Iter.any<Nat>([1, 2, 3].values(), func (x) = x == 4) // => false

public func find<T>(iter : Iter<T>, f : T -> Bool) : ?T

Finds the first element produced by an iterator for which a predicate function returns true. Returns null if no such element is found. It stops consuming elements from the original iterator as soon as the predicate returns true.

import Iter "mo:new-base/Iter";
Iter.find<Nat>([1, 2, 3, 4].values(), func (x) = x % 2 == 0) // => ?2

public func contains<T>(
  iter : Iter<T>,
  equal : (T, T) -> Bool,
  value : T
) : Bool

Checks if an element is produced by an iterator. It stops consuming elements from the original iterator as soon as the predicate returns true.

import Iter "mo:new-base/Iter";
import Nat "mo:new-base/Nat";
Iter.contains<Nat>([1, 2, 3].values(), Nat.equal, 2) // => true

public func foldLeft<T, R>(
  iter : Iter<T>,
  initial : R,
  combine : (R, T) -> R
) : R

Reduces an iterator to a single value by applying a function to each element and an accumulator. The accumulator is initialized with the initial value. It starts applying the combine function starting from the initial accumulator value and the first elements produced by the iterator.

import Iter "mo:new-base/Iter";
Iter.foldLeft<Text>(["A", "B", "C"].values(), "S", func (acc, x) = "(" # acc # x # ")") // => ?"(((SA)B)C)"

public func foldRight<T, R>(
  iter : Iter<T>,
  initial : R,
  combine : (T, R) -> R
) : R

Reduces an iterator to a single value by applying a function to each element in reverse order and an accumulator. The accumulator is initialized with the initial value and it is first combined with the last element produced by the iterator. It starts applying the combine function starting from the last elements produced by the iterator.

Performance note: Since this function needs to consume the entire iterator to reverse it, it has to materialize the entire iterator in memory to get to the last element to start applying the combine function. Use foldLeft or reduce when possible to avoid the extra memory overhead.

import Iter "mo:new-base/Iter";
Iter.foldRight<Text>(["A", "B", "C"].values(), "S", func (x, acc) = "(" # x # acc # ")") // => ?"(A(B(CS)))"

public func reduce<T>(iter : Iter<T>, combine : (T, T) -> T) : ?T

Reduces an iterator to a single value by applying a function to each element, starting with the first elements. The accumulator is initialized with the first element produced by the iterator. When the iterator is empty, it returns null.

import Iter "mo:new-base/Iter";
Iter.reduce<Nat>([1, 2, 3].values(), Nat.add) // => ?6

public func scanLeft<T, R>(
  iter : Iter<T>,
  initial : R,
  combine : (R, T) -> R
) : Iter<R>

Produces an iterator containing cumulative results of applying the combine operator going left to right, including the initial value.

import Iter "mo:new-base/Iter";
let iter = [1, 2, 3].values();
let scanned = Iter.scanLeft<Nat, Nat>(iter, 0, Nat.add);
Iter.toArray(scanned) // => [0, 1, 3, 6]

public func scanRight<T, R>(
  iter : Iter<T>,
  initial : R,
  combine : (T, R) -> R
) : Iter<R>

Produces an iterator containing cumulative results of applying the combine operator going right to left, including the initial value.

Performance note: Since this function needs to consume the entire iterator to reverse it, it has to materialize the entire iterator in memory to get to the last element to start applying the combine function. Use scanLeft when possible to avoid the extra memory overhead.

import Iter "mo:new-base/Iter";
let iter = [1, 2, 3].values();
let scanned = Iter.scanRight<Nat, Nat>(iter, 0, Nat.add);
Iter.toArray(scanned) // => [0, 3, 5, 6]

public func unfold<T, S>(initial : S, step : S -> ?(T, S)) : Iter<T>

Creates an iterator that produces elements using the step function starting from the initial value. The step function takes the current state and returns the next element and the next state, or null if the iteration is finished.

import Iter "mo:new-base/Iter";
let iter = Iter.unfold<Nat, Nat>(1, func (x) = if (x <= 3) ?(x, x + 1) else null);
Iter.toArray(iter) // => [1, 2, 3]

public func max<T>(iter : Iter<T>, compare : (T, T) -> Order.Order) : ?T

Consumes an iterator and returns the first maximum element produced by the iterator. If the iterator is empty, it returns null.

import Iter "mo:new-base/Iter";
Iter.max<Nat>([1, 2, 3].values(), Nat.compare) // => ?3

public func min<T>(iter : Iter<T>, compare : (T, T) -> Order.Order) : ?T

Consumes an iterator and returns the first minimum element produced by the iterator. If the iterator is empty, it returns null.

import Iter "mo:new-base/Iter";
Iter.min<Nat>([1, 2, 3].values(), Nat.compare) // => ?1

public func infinite<T>(item : T) : Iter<T>

Creates an iterator that produces an infinite sequence of x.

import Iter "mo:new-base/Iter";
let iter = Iter.make(10);
assert(?10 == iter.next());
assert(?10 == iter.next());
assert(?10 == iter.next());
// ...

public func concat<T>(a : Iter<T>, b : Iter<T>) : Iter<T>

Takes two iterators and returns a new iterator that produces elements from the original iterators sequentally.

import Iter "mo:new-base/Iter";
let iter1 = [1, 2].values();
let iter2 = [5, 6, 7].values();
let concatenatedIter = Iter.concat(iter1, iter2);
Iter.toArray(concatenatedIter) // => [1, 2, 5, 6, 7]

public func fromArray<T>(array : [T]) : Iter<T>

Creates an iterator that produces the elements of an Array in ascending index order.

import Iter "mo:new-base/Iter";
let iter = Iter.fromArray([1, 2, 3]);
assert(?1 == iter.next());
assert(?2 == iter.next());
assert(?3 == iter.next());
assert(null == iter.next());

public func fromVarArray<T>(array : [var T]) : Iter<T>

Like fromArray but for Arrays with mutable elements. Captures the elements of the Array at the time the iterator is created, so further modifications won't be reflected in the iterator.

public func toArray<T>(iter : Iter<T>) : [T]

Consumes an iterator and collects its produced elements in an Array.

import Iter "mo:new-base/Iter";
let iter = [1, 2, 3].values();
assert([1, 2, 3] == Iter.toArray(iter));

public func toVarArray<T>(iter : Iter<T>) : [var T]

Like toArray but for Arrays with mutable elements.

public func sort<T>(iter : Iter<T>, compare : (T, T) -> Order.Order) : Iter<T>

Sorted iterator. Will iterate over all elements to sort them, necessarily.

public func repeat<T>(item : T, count : Nat) : Iter<T>

Creates an iterator that produces a given item a specified number of times.

import Iter "mo:new-base/Iter";

let iter = Iter.repeat<Nat>(3, 2);
assert(?3 == iter.next());
assert(?3 == iter.next());
assert(null == iter.next());

Runtime: O(1)

Space: O(1)

public func reverse<T>(iter : Iter<T>) : Iter<T>

Creates a new iterator that produces elements from the original iterator in reverse order. Note: This function needs to consume the entire iterator to reverse it.

import Iter "mo:new-base/Iter";

let iter = Iter.fromArray([1, 2, 3]);
let reversed = Iter.reverse(iter);
assert(?3 == reversed.next());
assert(?2 == reversed.next());
assert(?1 == reversed.next());
assert(null == reversed.next());

Runtime: O(n) where n is the number of elements in the iterator

Space: O(n) where n is the number of elements in the iterator