RRB

RRB.Vec — persistent sequence for bulk-parallel work.

v2: backed by Array (32-way trie, O(1) amortised push, O(log₃₂ n) get).

A Slice is a zero-copy window into a Vec: Slice(arr, lo, hi). chunk(v, n) creates n Slices in O(n) — the underlying Array is shared. fold(s, z, f) iterates [lo, hi) using O(1)-amortised Array.get.

Complexity summary: empty, singleton, is_empty, length O(1) get, set O(log₃₂ n) push O(1) amortised concat(l, r) O(len(r) · log₃₂(len(l)+len(r))) slice(v, lo, hi) O(1) chunk(v, n) O(n) fold(slice, z, f) O((hi-lo) · log₃₂ n) from_list, to_list, tabulate, range O(n) map, fold_left, each O(n)

Examples

march> let vec = RRB.from_list([1, 2, 3, 4, 5])
march> RRB.length(vec)
5
march> let s = RRB.slice(vec, 1, 4)
march> RRB.fold(s, 0, fn (acc, x) -> acc + x)
9

Types

ptypeVecVec(a) = Vec(Array.PVec(a))#

Persistent sequence. Wraps the Array module's 32-way trie PVec. Constructors are private; use the public API below.

ptypeSliceSlice(a) = Slice(Array.PVec(a), Int, Int)#

Zero-copy contiguous window into a Vec: [lo, hi). Created by slice/chunk; iterated by fold.

Functions

fnchunkchunk(v: Vec(a), n: Int)#

Split v into n roughly equal contiguous Slices in index order. Returns an Array of Slices. Each Slice is a zero-copy view (O(1) to create). O(n) total.

Edge cases:

n <= 0 is treated as 1.
n > length(v) is clamped to length(v) (no empty slices).
Empty v returns an empty Array.

Examples

march> let v = RRB.range(0, 6)
march> Array.length(RRB.chunk(v, 3))
3

fnconcatconcat(l: Vec(a), r: Vec(a)): Vec(a)#

Concatenate two Vecs: all elements of l followed by all of r. O(len(r) · log₃₂(len(l)+len(r))).

Examples

march> RRB.to_list(RRB.concat(RRB.from_list([1,2]), RRB.from_list([3,4])))
[1, 2, 3, 4]

fneacheach(v: Vec(a), f: a -> Unit): Unit#

Apply f to each element in index order, for side effects. O(n).

Examples

RRB.each(RRB.from_list(["a", "b"]), fn s -> println(s))
-- prints a, then b

fnemptyempty(): Vec(a) do Vec(Array.empty()) end#

An empty Vec. O(1).

Examples

march> RRB.length(RRB.empty())
0

fnfoldfold(s: Slice(a), zero: b, f: b -> a -> b): b#

Left fold over a Slice in index order. f(acc, elem) = new_acc. O((hi-lo) · log₃₂ n).

This is the hot path inside each parallel worker: it visits only the elements in the slice's range without copying or allocating. Generic in the accumulator b, so a refinement demanded of the result is checked as an invariant of acc (see docs/refinement-types.md, "Folds").

Examples

march> let s = RRB.slice(RRB.range(0, 5), 1, 4)
march> RRB.fold(s, 0, fn (acc, x) -> acc + x)
6

fnfold_leftfold_left(v: Vec(a), zero: b, f: b -> a -> b): b#

Left fold over all elements. f(acc, elem) = new_acc. O(n). Generic in the accumulator b, so a refinement demanded of the result is checked as an invariant of acc (see docs/refinement-types.md, "Folds").

Examples

march> RRB.fold_left(RRB.from_list([1, 2, 3]), 0, fn (acc, x) -> acc + x)
6

fnfrom_arrayfrom_array(xs: Array.PVec(a)): Vec(a) do Vec(xs) end#

Wrap an Array (an Array.PVec(a), the type every Array.* function returns) as a Vec. O(1); the array is shared, not copied.

Examples

march> RRB.to_list(RRB.from_array(Array.from_list([1, 2, 3])))
[1, 2, 3]

fnfrom_listfrom_list(xs: List(a)): Vec(a) do Vec(Array.from_list(xs)) end#

Build a Vec from a list, preserving order. O(n).

Examples

march> RRB.get(RRB.from_list([10, 20, 30]), 2)
30
march> RRB.is_empty(RRB.from_list([]))
true

fngetget(v: Vec(a), i: Int): a#

Return element at 0-based index i. O(log₃₂ n). Panics if out of bounds.

Examples

march> RRB.get(RRB.from_list([10, 20, 30]), 1)
20

fnis_emptyis_empty(v: Vec(a)): Bool#

True when the Vec is empty. O(1).

Examples

march> RRB.is_empty(RRB.empty())
true
march> RRB.is_empty(RRB.singleton(0))
false

fnlengthlength(v: Vec(a)): Int#

Number of elements. O(1).

Examples

march> RRB.length(RRB.range(0, 40))
40
march> RRB.length(RRB.empty())
0

fnmapmap(v: Vec(a), f: a -> b): Vec(b)#

Apply f to every element, collecting results in a new Vec in the same order. O(n).

For parallel map, use Parallel.pmap instead — this is the sequential version.

Examples

march> RRB.to_list(RRB.map(RRB.from_list([1, 2, 3]), fn x -> x * 2))
[2, 4, 6]
march> RRB.length(RRB.map(RRB.empty(), fn x -> x + 1))
0

fnpushpush(v: Vec(a), x: a): Vec(a)#

Append x at the end. Returns a new Vec; the original is unchanged. O(1) amortised.

Examples

march> RRB.to_list(RRB.push(RRB.from_list([1, 2]), 3))
[1, 2, 3]
march> RRB.to_list(RRB.push(RRB.empty(), 1))
[1]

fnrangerange(lo: Int, hi: Int): Vec(Int)#

Build a Vec of consecutive integers [lo, lo+1, …, hi-1]. O(hi-lo).

Examples

march> RRB.to_list(RRB.range(1, 5))
[1, 2, 3, 4]

fnsingletonsingleton(x: a): Vec(a) do Vec(Array.push(Array.empty(), x)) end#

A Vec containing exactly one element. O(1).

Examples

march> RRB.to_list(RRB.singleton("x"))
["x"]

fnsliceslice(v: Vec(a), lo: Int, hi: Int): Slice(a)#

Create a Slice covering the half-open range [lo, hi). O(1).

Indices are clamped to [0, length(v)]; lo > hi (after clamping) yields an empty slice.

Examples

march> RRB.fold(RRB.slice(RRB.range(0, 5), 1, 4), 0, fn (a, x) -> a + x)
6

fnsort_bysort_by(v: Vec(a), le: a -> a -> Bool): Vec(a)#

Sort by a comparator, stably; see Array.sort_by. O(n log n).

Examples

march> RRB.to_list(RRB.sort_by(RRB.from_list([3, 1, 2]), fn (a, b) -> a <= b))
[1, 2, 3]

fnsort_by_keysort_by_key(v: Vec(a), key: a -> Int): Vec(a)#

Sort by an Int key computed once per element, stably; see Array.sort_by_key. O(n log n).

Examples

march> RRB.to_list(RRB.sort_by_key(RRB.from_list([30, 4, 200]), fn x -> 0 - x))
[200, 30, 4]

fntabulatetabulate(n: Int, f: Int -> a): Vec(a)#

Build a Vec of length n by calling f(i) for each index i ∈ [0, n). O(n).

Examples

march> RRB.to_list(RRB.tabulate(4, fn i -> i * i))
[0, 1, 4, 9]

fnto_arrayto_array(v: Vec(a)): Array.PVec(a)#

Return the underlying Array (an Array.PVec(a)). O(1); nothing is copied.

Examples

march> Array.to_list(RRB.to_array(RRB.from_list([1, 2, 3])))
[1, 2, 3]

fnto_listto_list(v: Vec(a)): List(a)#

Return all elements as a list in index order. O(n).

Examples

march> RRB.to_list(RRB.range(3, 6))
[3, 4, 5]
march> RRB.to_list(RRB.empty())
[]