🥮 mooncakes.io

    #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 0 when tree is Empty, and otherwise names the height of tree exactly: every operation that walks the tree is handed this shift and decrements it by NUM_BITS per level, so a Leaf must sit at shift 0.
    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]

    Concatenate two vectors.

    Aborts if the resulting length cannot be represented by Int.

    The result always takes other's tail, so the work is deciding what happens to self's. In order of cost:

    1. other.tree is Empty and the two tails fit in one chunk — splice the tails, leave self.tree alone. No tree work at all.
    2. Same, but the tails overflow — normalize_tree folds self's tail into its tree, then other's tail becomes the new tail.
    3. other has a tree and self has no tail — a plain Tree::concat.
    4. Both have substance — Tree::concat_with_suffix threads self's tail through the splice as an extra leaf, rather than normalizing first and concatenating in two passes. This is the case that can widen a merge to 65 children; see rebalance.

    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]

    Returns the vector itself. Since it is an immutable data structure, nothing is copied and there is no reason to call 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.

    Aborts if the iterator yields more elements than a Vector length can represent with Int.

    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.

    Aborts if the resulting length cannot be represented by Int.

    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