🥮 mooncakes.io
README

#Immutable Vector

An immutable (persistent) vector providing efficient random access, update, and append operations. Similar to Clojure's persistent vector, it uses a wide branching tree (branching factor 32) with a tail buffer to achieve near-constant-time operations on the right end.

This package replaces the removed immut/array package with a more efficient tail-backed layout.

#Overview

Vector[A] is a persistent data structure -- all "modification" operations return a new vector, leaving the original unchanged. Internally it stores elements in a 32-way trie with a separate tail buffer for the rightmost chunk, which makes push and pop effectively O(1) amortized.

#Performance

  • push / pop: Effectively O(1) amortized (O(log32 n) worst case)
  • get / set: O(log32 n) -- at most 7 levels for billions of elements
  • concat: O(log n)
  • split / slice / take / drop: O(log n)
  • iter / each / fold / map: O(n)
  • Space complexity: O(n), with structural sharing between versions

#Usage

#Create

Create an empty vector with new(), or construct one from an array or iterator.

///|
test {
  let v1 : @vector.Vector[Int] = @vector.new()
  @test.assert_eq(v1.length(), 0)
  let v2 = @vector.from_array([1, 2, 3, 4, 5])
  @test.assert_eq(v2.length(), 5)
  let v3 = @vector.from_iter((1).until(5))
  @debug.assert_eq(v3.to_array(), [1, 2, 3, 4])
}

Use make() to create a vector filled with a value, or makei() to generate values from a function.

///|
test {
  let v1 = @vector.make(5, 0)
  @debug.assert_eq(v1.to_array(), [0, 0, 0, 0, 0])
  let v2 = @vector.makei(5, fn(i) { i * i })
  @debug.assert_eq(v2.to_array(), [0, 1, 4, 9, 16])
}

#Get & Set

Use index syntax v[i] or at() for direct access. Use get() for a safe lookup that returns Option.

///|
test {
  let v = @vector.from_array([10, 20, 30, 40, 50])
  @test.assert_eq(v[2], 30)
  assert_true(v.get(2) == Some(30))
  assert_true(v.get(99) == None)
  assert_true(v.peek() == Some(50)) // last element
}

set() returns a new vector with the element at the given index replaced.

///|
test {
  let v1 = @vector.from_array([1, 2, 3])
  let v2 = v1.set(1, 20)
  @debug.assert_eq(v1.to_array(), [1, 2, 3]) // original unchanged
  @debug.assert_eq(v2.to_array(), [1, 20, 3])
}

#Push & Pop

push() appends an element; pop() removes the last element. Both return a new vector.

///|
test {
  let v1 = @vector.from_array([1, 2, 3])
  let v2 = v1.push(4)
  @debug.assert_eq(v2.to_array(), [1, 2, 3, 4])
  let v3 = v2.pop().unwrap()
  @debug.assert_eq(v3.to_array(), [1, 2, 3])
  // pop on empty vector returns None
  let empty : @vector.Vector[Int] = @vector.new()
  assert_true(empty.pop() == None)
}

#Concatenation

Use concat() or the + operator to join two vectors.

///|
test {
  let a = @vector.from_array([1, 2, 3])
  let b = @vector.from_array([4, 5, 6])
  @debug.assert_eq(a.concat(b).to_array(), [1, 2, 3, 4, 5, 6])
  @debug.assert_eq((a + b).to_array(), [1, 2, 3, 4, 5, 6])
}

#Range Operations

split(), take(), drop(), and slice() work on subranges without flattening the tree.

///|
test {
  let v = @vector.from_iter((0).until(10))
  // split at index: [0, index) and [index, len)
  let (left, right) = v.split(4)
  @debug.assert_eq(left.to_array(), [0, 1, 2, 3])
  @debug.assert_eq(right.to_array(), [4, 5, 6, 7, 8, 9])
  // take first n elements
  @debug.assert_eq(v.take(3).to_array(), [0, 1, 2])
  // drop first n elements
  @debug.assert_eq(v.drop(7).to_array(), [7, 8, 9])
  // slice [start, end)
  @debug.assert_eq(v.slice(2, 6).to_array(), [2, 3, 4, 5])
}

#Iteration

Use iter() to get an iterator, or each() / eachi() for direct traversal.

///|
test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  // iterator
  debug_inspect(v.iter().to_array(), content="[1, 2, 3, 4, 5]")
  // each
  let buf = []
  v.each(fn(x) { buf.push(x) })
  @debug.assert_eq(buf, [1, 2, 3, 4, 5])
  // eachi (with index)
  let pairs = []
  v.eachi(fn(i, x) { pairs.push((i, x)) })
  @debug.assert_eq(pairs, [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)])
}

#Fold & Map

fold() reduces the vector from left to right; rev_fold() goes right to left. map() transforms each element.

///|
test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  // sum via fold
  @test.assert_eq(v.fold(fn(acc, x) { acc + x }, init=0), 15)
  // reverse fold
  let result = v.rev_fold(fn(acc, x) { acc + x.to_string() }, init="")
  @test.assert_eq(result, "54321")
  // map
  @debug.assert_eq(v.map(fn(x) { x * 2 }).to_array(), [2, 4, 6, 8, 10])
}

#Query

///|
test {
  let v = @vector.from_array([1, 2, 3])
  @test.assert_eq(v.length(), 3)
  @test.assert_eq(v.is_empty(), false)
  let empty : @vector.Vector[Int] = @vector.new()
  @test.assert_eq(empty.is_empty(), true)
}

#Comparison & Equality

Vectors support == (element-wise equality) and compare() (shortlex order: shorter vectors are smaller; equal-length vectors compare element-by-element).

///|
test {
  let a = @vector.from_array([1, 2, 3])
  let b = @vector.from_array([1, 2, 3])
  let c = @vector.from_array([1, 2, 4])
  @test.assert_eq(a == b, true)
  @test.assert_eq(a == c, false)
  @test.assert_eq(a.compare(c) < 0, true)
}

#
Vector

source
type Vector[A]

Invariants:
  • shift = tree height * NUM_BITS. When it is 0, we are at the leaf level.
  • size = the total number of elements in tree and tail.
  • tail stores the right-most chunk and has at most BRANCHING_FACTOR elements.
  • tree stores the prefix before tail.
  • shift is not used when tree is Empty.
impl Add for Vector[A]
impl Compare for Vector[A]
impl Eq for Vector[A]
impl Hash for Vector[A]
impl Show for Vector[A]
impl ToJson for Vector[A]
impl Debug for Vector[A]
impl FromJson for Vector[A]

#
Vector::Vector

source
#as_free_fn(of, deprecated="Use from_array instead")
#alias(of, deprecated="Use from_array instead")
#as_free_fn(from_array)
#alias(from_array)
fn[A] Vector::Vector(arr : ArrayView[A]) -> Vector[A]

Create a persistent vector from an array.

Example

test {
  let v = @vector.Vector([1, 2, 3])
  @debug.assert_eq(v, @vector.from_array([1, 2, 3]))
}

#
Vector::add

source
fn[A] Vector::add(self : Vector[A], other : Vector[A]) -> Vector[A]

#
Vector::at

source
#alias("_[_]")
fn[A] Vector::at(self : Vector[A], index : Int) -> A

Get a value at the given index.

Examples

test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  inspect(v[0], content="1")
}

#
Vector::compare

source
fn[A : Compare + Eq] Vector::compare(self : Vector[A], other : Vector[A]) -> Int

#
Vector::concat

source
fn[A] Vector::concat(self : Vector[A], other : Vector[A]) -> Vector[A]

Given two trees, concatenate them into a new tree.

#
Vector::contains

source
fn[A : Eq] Vector::contains(self : Vector[A], value : A) -> Bool

Returns true if the vector contains the given value.

Example

test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  inspect(v.contains(3), content="true")
  inspect(v.contains(6), content="false")
}

#
Vector::copy

source
#alias(clone, deprecated="`clone` is deprecated, use `copy` instead")
#deprecated("We don't copy immutable vector")
fn[A] Vector::copy(self : Vector[A]) -> Vector[A]

Physically copy the vector. Since it is an immutable data structure, it is rarely the case that you would need this function.

#
Vector::drop

source
fn[A] Vector::drop(self : Vector[A], count : Int) -> Vector[A]

Drop the first count elements.

#
Vector::each

source
fn[A] Vector::each(self : Vector[A], f : (A) -> Unit raise?) -> Unit raise?

Iterate over the vector.

Example

test {
  let arr = []
  let v = @vector.from_array([1, 2, 3, 4, 5])
  v.each(e => arr.push(e))
  @debug.assert_eq(arr, [1, 2, 3, 4, 5])
}

#
Vector::eachi

source
fn[A] Vector::eachi(self : Vector[A], f : (Int, A) -> Unit raise?) -> Unit raise?

Iterate over the vector with index.

Example

test {
  let arr = []
  let v = @vector.from_array([1, 2, 3, 4, 5])
  v.eachi((i, e) => arr.push(i * e))
  @debug.assert_eq(arr, [0, 2, 6, 12, 20])
}

#
Vector::equal

source
fn[A : Eq] Vector::equal(self : Vector[A], other : Vector[A]) -> Bool

#
Vector::filter

source
fn[A] Vector::filter(self : Vector[A], f : (A) -> Bool raise?) -> Vector[A] raise?

Creates a new vector containing only the elements that satisfy the predicate.

Example

test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  @debug.assert_eq(v.filter(x => x % 2 == 0), @vector.from_array([2, 4]))
}

#
Vector::fold

source
#alias(fold_left, deprecated="`fold_left` is deprecated, use `fold` instead")
fn[A, B] Vector::fold(self : Vector[A], init~ : B, f : (B, A) -> B raise?) -> B raise?

Fold the vector.

Example

test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  @test.assert_eq(v.fold((a, b) => a + b, init=0), 15)
}

#
Vector::from_iter

source
#as_free_fn(from_iterator, deprecated="Use Vector::from_iter instead.")
#alias(from_iterator, deprecated="`from_iterator` is deprecated, use `from_iter` instead")
#as_free_fn
fn[A] Vector::from_iter(iter : Iter[A]) -> Vector[A]

Creates an immutable vector from an iterator of values.

#
Vector::get

source
fn[A] Vector::get(self : Vector[A], index : Int) -> A?

Returns the element at the specified index in the vector, wrapped in an Option type.

Parameters:

  • vector : The immutable vector.
  • index : The index of the element to retrieve.

Returns Some(value) if the index is valid, None if the index is out of bounds.

Example:

test {
  let v = @vector.from_array([1, 2, 3])
  debug_inspect(v.get(1), content="Some(2)")
  debug_inspect(v.get(-1), content="None")
  debug_inspect(v.get(3), content="None")
}

#
Vector::hash

source
fn[A : Hash] Vector::hash(self : Vector[A]) -> Int

#
Vector::is_empty

source
fn[A] Vector::is_empty(self : Vector[A]) -> Bool

Returns true if the vector contains no elements.

#
Vector::iter

source
#alias(iterator, deprecated="`iterator` is deprecated, use `iter` instead")
fn[A] Vector::iter(self : Vector[A]) -> Iter[A]

Returns an iterator over the elements of the vector.

#
Vector::length

source
fn[A] Vector::length(self : Vector[A]) -> Int

Returns the number of elements in the vector.

#
Vector::make

source
#as_free_fn
fn[A] Vector::make(len : Int, value : A) -> Vector[A]

Create a persistent vector with a given length and value.

#
Vector::makei

source
#as_free_fn
fn[A] Vector::makei(len : Int, f : (Int) -> A raise?) -> Vector[A] raise?

Create a persistent vector with a given length and a function to generate values.

#
Vector::map

source
fn[A, B] Vector::map(self : Vector[A], f : (A) -> B raise?) -> Vector[B] raise?

Map a function over the vector.

Example

test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  @debug.assert_eq(v.map(e => e * 2), @vector.from_array([2, 4, 6, 8, 10]))
}

#
Vector::new

source
#as_free_fn
fn[A] Vector::new() -> Vector[A]

Return a new empty vector

#
Vector::peek

source
fn[A] Vector::peek(self : Vector[A]) -> A?

Returns the last element in the vector.

#
Vector::pop

source
fn[A] Vector::pop(self : Vector[A]) -> Vector[A]?

Remove the last element from the vector.

#
Vector::push

source
fn[A] Vector::push(self : Vector[A], value : A) -> Vector[A]

Push a value to the end of the vector.

Example

test {
  let v = @vector.from_array([1, 2, 3])
  @debug.assert_eq(v.push(4), @vector.from_array([1, 2, 3, 4]))
}

#
Vector::rev

source
fn[A] Vector::rev(self : Vector[A]) -> Vector[A]

Returns a new vector with the elements in reverse order.

Example

test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  @debug.assert_eq(v.rev(), @vector.from_array([5, 4, 3, 2, 1]))
}

#
Vector::rev_fold

source
#alias(fold_right, deprecated="`fold_right` is deprecated, use `rev_fold` instead")
fn[A, B] Vector::rev_fold(self : Vector[A], init~ : B, f : (B, A) -> B raise?) -> B raise?

Fold the vector in reverse order.

Example

test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  @test.assert_eq(v.rev_fold((a, b) => a + b, init=0), 15)
}

#
Vector::set

source
fn[A] Vector::set(self : Vector[A], index : Int, value : A) -> Vector[A]

Set a value at the given index (immutable).

Example

test {
  let v = @vector.from_array([1, 2, 3, 4, 5])
  @debug.assert_eq(v.set(1, 10), @vector.from_array([1, 10, 3, 4, 5]))
}

#
Vector::singleton

source
#as_free_fn
fn[A] Vector::singleton(value : A) -> Vector[A]

Create a vector with a single element.

Example

test {
  let v = @vector.singleton(42)
  @debug.assert_eq(v, @vector.from_array([42]))
  @test.assert_eq(v.length(), 1)
}

#
Vector::slice

source
fn[A] Vector::slice(self : Vector[A], start : Int, end : Int) -> Vector[A]

Return the slice [start, end).

#
Vector::split

source
fn[A] Vector::split(self : Vector[A], index : Int) -> (Vector[A], Vector[A])

Split the vector into [0, index) and [index, len).

#
Vector::take

source
fn[A] Vector::take(self : Vector[A], count : Int) -> Vector[A]

Return the first count elements.

#
Vector::to_array

source
fn[A] Vector::to_array(self : Vector[A]) -> Array[A]

Returns a mutable array containing all elements.

Source Files

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io