LEVIATHAN v962456e · 962456eee1

Standard Library

class Seq<T>

A lazy sequence: a pipeline of steps that does no work until its result is requested.

since 0.1.0-alpha.1linuxwindowswasm

bases
IIterable<T>

Overview

Arrays are eager, meaning each method such as map finishes over the whole array before the next step starts. A Seq is the lazy alternative. Get one from Array.asSeq(), chain the combinators map, where, take, takeWhile and skip (each only describes a step and runs nothing), and finish with a terminal operation: toArray, firstOrNone, count, forEach or reduce. Only then are elements pulled through, one at a time, and each function runs at most once per element that is actually pulled. take(n) and firstOrNone stop pulling early, so they work even when later elements are expensive or never needed.

A terminal operation needs the sequence to be finite; take is the way to bound one that is not. Running a terminal operation again on the same Seq starts over from the beginning of an array-backed pipeline.

Description

Arrays are eager: map and where on an Array run to completion and return a new array. Seq<T> is the lazy alternative. array.asSeq() turns an array into a Seq, and any IIterable<T> can join a pipeline by wrapping it in IterableSeq.

A Seq has two kinds of methods.

  • Combinators return another Seq and do no work: map, where, take, takeWhile and skip.
  • Terminals pull elements through the pipeline and return a result: toArray, firstOrNone, count, forEach and reduce.

Nothing runs until a terminal asks for an element. Then each element is pulled through the whole pipeline one at a time, so a function given to map or where runs at most once per element that is actually pulled. firstOrNone pulls only until it has one element, and take(n) stops pulling after n.

Evaluation order is element by element

Array<int> nums = [1, 2, 3, 4, 5, 6, 7];
Array<int> r = nums.asSeq()
    .map((x) => { console.writeln("square ${x}"); return x * x; })
    .where((x) => { console.writeln("odd? ${x}"); return x % 2 == 1; })
    .take(2)
    .toArray();
console.writeln(r);
Run it ▶
square 1
odd? 1
square 2
odd? 4
square 3
odd? 9
[1, 9]

The trace shows that each element goes through map and then where before the next element starts, and that the pipeline stops as soon as take(2) has its two results: the source elements 4 to 7 are never visited.

A Seq does not store its results. Each terminal call starts again from the source, so calling two terminals on the same Seq runs its functions twice. Call toArray() once if you need to reuse the elements.

Terminals need a finite source. A source that never ends is made finite with take(n) (or takeWhile); there is no guard against a terminal on an endless source, the same as a while (true) loop has none.

Laziness and terminals

Array<int> nums = [1, 2, 3, 4];
Seq<int> lazy = nums.asSeq().map((x) => { console.writeln("map ${x}"); return x * 10; });
console.writeln("built");
int? first = lazy.firstOrNone();
console.writeln(first);
console.writeln(lazy.count());
console.writeln(lazy.take(2).toArray());
console.writeln(nums.asSeq().takeWhile((x) => x < 3).toArray());
console.writeln(nums.asSeq().skip(1).reduce(0, (a, x) => a + x));
Run it ▶
built
map 1
10
map 1
map 2
map 3
map 4
4
map 1
map 2
[10, 20]
[1, 2]
9

Rules

  • Combinators (map, where, take, takeWhile, skip) are lazy and pull nothing.
  • Terminals (toArray, firstOrNone, count, forEach, reduce) drive the pipeline.
  • A map or where function runs at most once per pulled element, and elements are pulled one at a time through the whole pipeline.
  • firstOrNone pulls exactly as many elements as it needs to find one.
  • A terminal on an unbounded source never returns; bound the source with take.
  • Each terminal re-runs the pipeline from the source. Nothing is cached.
  • Pipelines are pure over their source: the array or iterable you start from is not changed.

Examples

Taking from an endless iterable

class Naturals : IIterable<int> {
    IIterator<int> iterator() => NaturalsIterator();
}
class NaturalsIterator : IIterator<int> {
    int cur = 0;
    bool hasNext() => true;
    int next() { cur = cur + 1; return cur; }
}
Seq<int> naturals = IterableSeq(Naturals());
console.writeln(naturals.where((n) => n % 2 == 0).take(3).toArray());
Array<int> eager = [1, 2, 3].map((x) => { console.writeln("eager ${x}"); return x; });
console.writeln(eager.length());
Run it ▶
[2, 4, 6]
eager 1
eager 2
eager 3
3

Notes

Each Seq stage wraps its source and pulls from it through the IIterable/IIterator interfaces, which is why any type that implements the iterator protocol can feed a pipeline.

Examples

Laziness shown by a trace

Array<int> nums = [1, 2, 3, 4, 5, 6];
Seq<int> pipeline = nums.asSeq()
    .where((x) => {
        console.writeln("check ${x}");
        return x % 2 == 0;
    })
    .map((x) => x * 10)
    .take(2);
console.writeln("built, nothing has run yet");
console.writeln(pipeline.toArray());
Run it ▶
built, nothing has run yet
check 1
check 2
check 3
check 4
[20, 40]

Methods

count

count() -> int

Run the pipeline and count how many elements it produces.

This is a terminal operation that pulls every element. The sequence must be finite.

Returns

The number of elements produced.

Examples

Counting matches

Seq<int> s = [1, 2, 3, 4, 5, 6].asSeq().where((x) => x % 3 == 0);
console.writeln(s.count());
Run it ▶
2

firstOrNone

firstOrNone() -> T | None

Run the pipeline just far enough to produce its first element.

This is a terminal operation that pulls exactly one element through the steps, so the rest of the source is never examined.

Returns

The first element, or None when the sequence is empty.

Examples

Short-circuiting

Seq<int> s = [5, 6, 7].asSeq().map((x) => {
    console.writeln("map ${x}");
    return x + 1;
});
console.writeln(s.firstOrNone());
console.writeln([1].asSeq().skip(1).firstOrNone());
Run it ▶
map 5
6
None

forEach

forEach((T) => void fn) -> void

Run the pipeline and call fn on every element it produces, in order.

This is a terminal operation that pulls every element. The sequence must be finite.

Parameters

fn
The action to perform on each element.

Examples

Printing as elements arrive

[1, 2, 3].asSeq().map((x) => x * 2).forEach((x) => console.writeln("got ${x}"));
Run it ▶
got 2
got 4
got 6

iterator

iterator() -> IIterator<T>

Return an iterator over the sequence, starting from the beginning.

Every sequence that asSeq and the combinators produce implements this. The base Seq class is abstract: a class you write that extends Seq must override iterator(), and the base version throws.

Returns

An iterator that yields the elements of the sequence lazily.

Throws

RuntimeException
when called on a Seq that does not override it.

Examples

Pulling elements by hand

Seq<int> s = [10, 20, 30].asSeq().map((x) => x + 1);
IIterator<int> it = s.iterator();
while (it.hasNext()) {
    console.writeln(it.next());
}
Run it ▶
11
21
31

map

map<U>((T) => U fn) -> Seq<U>

Return a lazy sequence of fn applied to each element.

Nothing is computed until a terminal operation pulls elements. The element type of the result may differ from T.

Parameters

fn
The transformation applied to each pulled element.

Returns

A new lazy sequence.

Examples

Map is not run until pulled

Seq<string> s = [1, 2, 3].asSeq().map((x) => {
    console.writeln("map ${x}");
    return "n" + x.toString();
});
console.writeln("created");
console.writeln(s.firstOrNone());
Run it ▶
created
map 1
n1

See also: map

reduce

reduce<A>(A seed, (A, T) => A fn) -> A

Run the pipeline and fold its elements into one value, from first to last.

This is a terminal operation that pulls every element. The sequence must be finite. An empty sequence returns seed.

Parameters

seed
The starting value of the accumulator.
fn
Combines the accumulator so far with the next element and returns the new accumulator.

Returns

The final accumulator.

Examples

Summing a filtered sequence

int total = [1, 2, 3, 4].asSeq().where((x) => x > 1).reduce(0, (sum, x) => sum + x);
console.writeln(total);
Run it ▶
9

skip

skip(int n) -> Seq<T>

Return a lazy sequence that leaves out the first n elements.

If the source has n or fewer elements the result is empty. The skipped elements are still pulled from the source, and any functions earlier in the pipeline still run for them.

Parameters

n
How many leading elements to drop.

Returns

A new lazy sequence.

Examples

Skipping a prefix

Seq<int> s = [1, 2, 3, 4, 5].asSeq().skip(3);
console.writeln(s.toArray());
console.writeln([1, 2].asSeq().skip(5).toArray());
Run it ▶
[4, 5]
[]

See also: take

take

take(int n) -> Seq<T>

Return a lazy sequence of at most the first n elements.

Once n elements have been produced, no further elements are pulled from the source, which makes take the way to bound a long or expensive pipeline.

Parameters

n
The maximum number of elements to produce.

Returns

A new lazy sequence.

Examples

Pulling only what is needed

Seq<int> s = [1, 2, 3, 4, 5].asSeq().map((x) => {
    console.writeln("map ${x}");
    return x * x;
}).take(2);
console.writeln(s.toArray());
Run it ▶
map 1
map 2
[1, 4]

See also: skip

takeWhile

takeWhile((T) => bool pred) -> Seq<T>

Return a lazy sequence of the leading elements for which pred is true.

The sequence ends at the first element that fails pred; elements after it are never examined.

Parameters

pred
The test applied to each pulled element, in order.

Returns

A new lazy sequence.

Examples

Stopping at the first failure

Seq<int> s = [1, 2, 9, 3].asSeq().takeWhile((x) => x < 5);
console.writeln(s.toArray());
Run it ▶
[1, 2]

See also: takeWhile

toArray

toArray() -> Array<T>

Run the pipeline and collect every element into an array.

This is a terminal operation: it pulls every element through all the steps. The sequence must be finite.

Returns

A new array of the elements, in order.

Examples

Collecting

Array<int> a = [1, 2, 3, 4].asSeq().where((x) => x % 2 == 1).map((x) => x * 100).toArray();
console.writeln(a);
Run it ▶
[100, 300]

where

where((T) => bool pred) -> Seq<T>

Return a lazy sequence of the elements for which pred is true.

Nothing is computed until a terminal operation pulls elements.

Parameters

pred
The test applied to each pulled element.

Returns

A new lazy sequence.

Examples

Filtering lazily

Seq<int> s = [1, 2, 3, 4, 5].asSeq().where((x) => x > 2);
console.writeln(s.toArray());
console.writeln(s.count());
Run it ▶
[3, 4, 5]
3

See also: where

See also

  • asSeq — View the array as a lazy Seq.
  • The iterator protocol — IIterable and IIterator — Two interfaces that make any type usable in a for-in loop, and the rules for which loop path the compiler picks.
  • Array — An ordered sequence of values of one type, Array<T>, with value semantics.
  • IIterable — A source of values that can be walked with for.