Sequence

A sequence is an ordered collection of elements where each element has a defined position. In ribs, all sequence types mix in RSeq<A>, which extends RIterable<A> and adds two foundational operations: indexed access via operator [] and a length property.

This page describes every concrete sequence type in ribs, what makes each one distinct, and when to reach for one over another.

The Sequence Hierarchy

RSeq<A>                  ordered, has length and operator []
  ├── IndexedSeq<A>       efficient random access — O(log n) or better
  │     ├── IVector<A>    general-purpose immutable sequence (finger tree)
  │     └── Range         integer range, no element storage
  ├── IList<A>            immutable linked list; fast prepend
  ├── IChain<A>           immutable; O(1) append, prepend, concat
  ├── NonEmptyIList<A>    IList guaranteed non-empty by the type system
  ├── IQueue<A>           immutable FIFO queue; amortised O(1) enqueue/dequeue
  ├── ILazyList<A>        lazily evaluated sequence; supports infinite lists
  └── ListBuffer<A>       mutable sequence; converts to IList

IndexedSeq<A> is a sub-mixin of RSeq<A> that additionally promises efficient random access. IVector and Range mix it in; the others do not.

Immutable Sequences

IList

IList<A> is a persistent singly-linked list. It is the simplest and most common sequence type in ribs.

Structural properties:

prepended / prependedAll — O(1); adding to the front is the natural operation
appended / appendedAll — O(n); avoids use where frequent tail-append is needed
head / tail — O(1)
operator [] — O(n); random access requires walking the list
Sequential traversal — O(n) but with low constant factor

Construction:

IList Constructors

final ilistEmpty = IList.empty<int>();
final ilistFromLiteral = ilist([1, 2, 3]);
final ilistFromDart = IList.fromDart([4, 5, 6]);
final ilistFilled = IList.fill(5, 'x');
final ilistTabulated = IList.tabulate(5, (int i) => i * i); // [0, 1, 4, 9, 16]
final ilistRanged = IList.range(0, 5); // [0, 1, 2, 3, 4]

Use when:

Building a list by repeatedly prepending (e.g. accumulating results via foldLeft)
Passing collections to recursive or pattern-matched code
The collection will be traversed sequentially from front to back
You want a simple, lightweight immutable list with a small memory footprint

Avoid when:

You frequently access elements by index — use IVector instead
You frequently append to the end — use IChain or IVector instead

IVector

IVector<A> is a persistent finger-tree vector. It is the general-purpose immutable sequence for situations where IList is not the best fit.

Structural properties:

operator [] — effectively O(1) (O(log₃₂ n) in theory, constant in practice for all realistic sizes)
appended — effectively O(1) amortised
prepended — effectively O(1) amortised
updated(index, elem) — effectively O(1)
Sequential traversal — O(n)

IVector also mixes in IndexedSeq, meaning methods like sorted, sortBy, and sortWith are available directly and operate on the indexed structure.

Construction:

IVector Constructors

final ivectorEmpty = IVector.empty<int>();
final ivectorFromLiteral = ivec([1, 2, 3]);
final ivectorFromDart = IVector.fromDart([4, 5, 6]);
final ivectorFilled = IVector.fill(5, 0);

For incremental construction, use IVector.builder(), which returns an IVectorBuilder<A>. Call addOne for each element, then result() to produce the final immutable vector:

IVector Builder

IVector<String> buildVector() => IVector.builder<String>().addOne('a').addOne('b').result();

Use when:

You need frequent indexed access (vec[i])
You need to append or prepend elements regularly
You need updated without copying the whole collection
You don't know ahead of time whether access will be sequential or random
In doubt, IVector is the safe default for a general-purpose immutable sequence

Avoid when:

You are building purely by prepending — IList is simpler and more idiomatic
You need O(1) concat of large collections — use IChain

IChain

IChain<A> is an immutable sequence optimised for structural operations that are expensive on linked lists and vectors alike.

Structural properties:

appended — O(1)
prepended — O(1)
concat — O(1); joining two chains never copies either side
operator [] — O(n); random access is slow
Sequential traversal — O(n) but with a higher constant than IList

Internally, IChain is a tree of wrapped sequences. It defers all structural combination into a lazy tree and only materialises elements during traversal. This makes it ideal for building up large results incrementally without any intermediate copying.

Construction:

final ichainEmpty = IChain.empty<int>();
final ichainSingle = IChain.one(42);
final ichainFromLiteral = ichain([1, 2, 3]);
final ichainFromDart = IChain.fromDart([4, 5, 6]);
final ichainFromSeq = IChain.fromSeq(ilist([7, 8, 9]));

Use when:

Accumulating results by repeated appended, prepended, or concat
Combining many sub-sequences together (e.g. building up a document or log from many small parts)
The final collection will be converted to IList or IVector at the end

Avoid when:

You need efficient random access during processing — convert to IVector first
The collection is small and simple — IList or IVector have less overhead

NonEmptyIList

NonEmptyIList<A> is an IList that is guaranteed by the type system to contain at least one element. It has a mandatory head field and an IList tail.

The key difference from IList: The compiler enforces non-emptiness. head is always defined — it is a field, not a method that might throw. Any function that requires at least one element can encode that requirement in its signature instead of checking at runtime.

Construction:

final nelBasic = nel(1, [2, 3, 4]);
final nelSingle = nel(1);
final nelWithTail = NonEmptyIList<int>(1, ilist([2, 3]));
final nelFromOpt = NonEmptyIList.fromDart([1, 2, 3]); // Some(nel(1, [2, 3]))
final nelFromEmpty = NonEmptyIList.fromDart<int>([]); // None

NonEmptyIList.from and fromDart return Option<NonEmptyIList<A>> — None when the input is empty, Some when it is not. This is the safe way to promote an arbitrary collection to a NonEmptyIList.

Use when:

A function must receive at least one element and you want to express that constraint in the type, not via a runtime check or a documentation note
You are accumulating validation errors and want to guarantee at least one is present before reporting them
Any situation where an empty result would be a programming error rather than a normal case

Range

Range represents an integer sequence defined by start, end, and step — without storing any elements. All elements are computed on demand from these three values.

Range mixes in IndexedSeq<int>, so it supports fast indexed access and all the operations of a full sequence, including map, filter, foldLeft, toIList, etc. Transforming a Range materialises it into the appropriate concrete type.

Construction:

final rangeExclusive = Range.exclusive(0, 10); // 0, 1, 2, …, 9
final rangeInclusive = Range.inclusive(0, 10); // 0, 1, 2, …, 10
final rangeStepped = Range.exclusive(0, 10, 2); // 0, 2, 4, 6, 8
final rangeRestepped = Range.exclusive(0, 10).by(3); // 0, 3, 6, 9

Use when:

Iterating over a sequence of integers without allocating a collection
Generating indices to use in other operations
The sequence is dense and regular enough to be described by start/end/step

IQueue

IQueue<A> is an immutable first-in, first-out queue implemented as two IList stacks. It provides amortised O(1) enqueue and dequeue.

enqueue adds an element to the back and returns a new IQueue. dequeue removes the front element, returning both the element and the remaining queue as a tuple. Use dequeueOption to avoid throwing on an empty queue:

void iQueueExample() {
  final empty = IQueue.empty<String>();
  final withFirst = empty.enqueue('hello');
  final withSecond = withFirst.enqueue('world');

  // dequeue returns a tuple of (front element, remaining queue)
  final (front, rest) = withSecond.dequeue();
  print(front); // hello
  print(rest); // IQueue containing 'world'

  // dequeueOption returns None on an empty queue instead of throwing
  final safeDequeue = IQueue.empty<String>().dequeueOption(); // None
  print(safeDequeue);
}

Use when:

You need FIFO semantics — elements should be processed in the order they arrived
Both the front and the back of the collection are active (e.g. a work queue, a BFS frontier, a message buffer)

Avoid when:

You only need stack semantics (LIFO) — IList.prepended / head / tail is sufficient
Random access is required — IVector is a better fit

ILazyList

ILazyList<A> is a lazily evaluated sequence. Elements are not computed until they are accessed. This makes it possible to represent infinite sequences that are only materialised as far as needed.

Each element is computed on first access and memoised — repeated access to the same position is free. All standard RSeq operations (map, filter, take, etc.) remain lazy until a terminal operation like toIList or foreach forces evaluation.

Construction:

final lazyEmpty = ILazyList.empty<int>();
final lazyInfinite = ILazyList.continually(1); // 1, 1, 1, ...
final lazyFilled = ILazyList.fill(5, 'x');
final lazyFromList = ILazyList.from(ilist([1, 2, 3]));

// Take only what you need from an infinite list
final first10 = lazyInfinite.take(10).toIList(); // IList of ten 1s

Use when:

You need an infinite or very large sequence and only a bounded prefix will ever be consumed (use take(n) to materialise what you need)
Computation of elements is expensive and you want to avoid doing work for elements that are never accessed
Memoisation of computed elements is desirable

Avoid when:

The whole sequence will always be consumed — a strict IVector or IList is simpler and avoids the laziness overhead
Memory is a concern — memoised elements are retained in memory once computed

Mutable Sequences

ListBuffer

ListBuffer<A> is the mutable counterpart to IList. It is backed by a mutable singly-linked list and supports efficient mutation during construction, after which it can be converted to an immutable IList in O(1).

The idiomatic way to obtain a ListBuffer is via IList.builder<A>(). Call addOne or addAll to populate it, then toIList() to produce the final immutable result:

void listBufferExample() {
  final buf = IList.builder<int>();
  buf.addOne(1);
  buf.addOne(2);
  buf.addAll(ilist([3, 4, 5]));

  // O(1) conversion — no copying
  final immutableList = buf.toIList(); // IList([1, 2, 3, 4, 5])
  print(immutableList);
}

The conversion via toIList is O(1) — the resulting IList shares structure with the buffer without copying.

Use when:

Building an IList incrementally by appending many elements, where constructing the list with repeated prepended calls would require reversal at the end
Inside an algorithm that needs mutation for performance but should return an immutable result

Avoid when:

The final result will be used as an IVector — use IVector.builder() instead
Mutation is not needed — use IList or IChain directly

Choosing a Sequence Type

Requirement	Recommended type
Default immutable list	`IVector`
Fast prepend, sequential traversal	`IList`
O(1) append and concat; building incrementally	`IChain`
At least one element, enforced by the compiler	`NonEmptyIList`
Dense integer iteration without allocation	`Range`
FIFO queue semantics	`IQueue`
Potentially infinite or lazily computed sequence	`ILazyList`
Incrementally building an `IList` from many appends	`ListBuffer`

Additional Operations on RSeq

All sequence types inherit the full RIterableOnce and RIterable APIs. In addition, RSeq provides operations that only make sense on ordered, indexed collections:

Member	Description
`operator [](i)`	Element at index `i`; throws if out of bounds
`lift(i)`	Element at index `i` as `Some`, or `None` if out of bounds
`length`	Number of elements
`indices()`	A `Range` of all valid indices
`isDefinedAt(i)`	`true` if `i` is a valid index
`indexOf(elem)`	`Some(index)` of first occurrence, or `None`
`indexWhere(p)`	`Some(index)` of first element satisfying `p`, or `None`
`lastIndexOf(elem)`	`Some(index)` of last occurrence, or `None`
`lastIndexWhere(p)`	`Some(index)` of last element satisfying `p`, or `None`
`indexOfSlice(that)`	`Some(index)` of first occurrence of sub-sequence `that`, or `None`
`contains(elem)`	`true` if any element equals `elem`
`containsSlice(that)`	`true` if `that` appears as a contiguous sub-sequence
`startsWith(that)`	`true` if this sequence begins with `that`
`endsWith(that)`	`true` if this sequence ends with `that`
`prepended(elem)`	New sequence with `elem` at the front
`prependedAll(prefix)`	New sequence with `prefix` added at the front
`appended(elem)`	New sequence with `elem` at the back
`appendedAll(suffix)`	New sequence with `suffix` added at the back
`updated(i, elem)`	New sequence with element at `i` replaced
`patch(from, elems, n)`	Replace `n` elements starting at `from` with `elems`
`removeAt(i)`	New sequence with the element at `i` removed
`removeFirst(p)`	New sequence with the first element satisfying `p` removed
`diff(that)`	Elements in this sequence but not in `that`
`intersect(that)`	Elements in both this sequence and `that`
`distinct()`	New sequence with duplicate elements removed
`distinctBy(f)`	New sequence with duplicates removed, keyed by `f`
`intersperse(sep)`	New sequence with `sep` inserted between each pair of elements
`padTo(len, elem)`	Extend to at least `len` elements by appending `elem`
`reverse()`	New sequence with elements in reverse order
`reverseIterator()`	An iterator over elements in reverse order
`sorted(order)`	New sequence sorted by `order`
`sortBy(order, f)`	New sequence sorted by `order` applied to `f(elem)`
`sortWith(lt)`	New sequence sorted using a less-than function
`combinations(n)`	Iterator of all distinct size-`n` combinations
`permutations()`	Iterator of all distinct permutations
`sameElements(that)`	`true` if both sequences have the same elements in the same order
`corresponds(that, p)`	`true` if elements correspond pairwise under `p`
`findLast(p)`	Last element satisfying `p` as `Some`, or `None`
`segmentLength(p, from)`	Length of the longest prefix starting at `from` where all elements satisfy `p`
`traverseEither(f)`	Apply `f` to each element; return `Left` on first failure or `Right` of all results
`traverseOption(f)`	Apply `f` to each element; return `None` on first absent result or `Some` of all

The Sequence Hierarchy​

Immutable Sequences​

IList​

IVector​

IChain​

NonEmptyIList​

Range​

IQueue​

ILazyList​

Mutable Sequences​

ListBuffer​

Choosing a Sequence Type​

Additional Operations on RSeq​

The Sequence Hierarchy

Immutable Sequences

IList

IVector

IChain

NonEmptyIList

Range

IQueue

ILazyList

Mutable Sequences

ListBuffer

Choosing a Sequence Type

Additional Operations on RSeq