becca.monster / iv
a fast, general-purpose, persistent array structure for Gleam.
22
Fork 0

Configure Feed

Select the types of activity you want to include in your feed.

Gleam 82.3%
Erlang 14.8%
Python 2.2%
JavaScript 0.6%
Other 0.2%
99 1 17

Clone this repository

https://tangled.org/becca.monster/iv https://tangled.org/did:plc:qohhzzqxsvtgf2kud2bzvw57
git@tangled.org:becca.monster/iv git@tangled.org:did:plc:qohhzzqxsvtgf2kud2bzvw57

For self-hosted knots, clone URLs may differ based on your setup.


Download tar.gz Download .zip
README.md

iv#

Package Version Hex Docs

iv is a fast, general-purpose, persistent array structure for Gleam.

You can use it like you would use an array in other programming languages and expect comparable or better runtime characteristics. It offers O(log n) or effectively constant runtime on all main operations, including concat and split, making it an excellent choice when parallelising workloads.

Benchmarks#

iv does not try to be the fastest at anything, but offer consistent, high performance across all types of workloads.

You can find benchmarks here.

Installation#

gleam add iv@1

Example: Bubble-Sort#

import iv
import gleam/int

// bubble sort, in my gleam?
pub fn main() {
  // make an array of 10 random integers
  let array = iv.initialise(10, fn(_) { int.random(100) })
  let sorted = bubble_sort(array)

  use item <- iv.each(sorted)

  io.println(int.to_string(item))
}

fn bubble_sort(array) {
  bubble_sort_loop(array, 1, iv.size(array))
}

fn bubble_sort_loop(array, index, max_index) {
  case iv.get(array, index - 1), iv.get(array, index) {
    // found 2 elements in the wrong order, swap them, then continue
    Ok(prev), Ok(curr) if prev > curr -> {
      let array =
        array
        |> iv.try_set(index, prev)
        |> iv.try_set(index - 1, curr)
      bubble_sort_loop(array, index + 1, max_index)
    }

    // found 2 elements in the correct order, we can skip them!
    Ok(_), Ok(_) if index < max_index ->
      bubble_sort_loop(array, index + 1, max_index)

    // reached the end, decrease max_index then try again!
    _, _ if max_index > 2 -> bubble_sort_loop(array, 1, max_index - 1)

    // reached the end and no more elements to swap, we are done.
    _, _ -> array
  }
}

Further documentation can be found at https://hexdocs.pm/iv.

Development#

gleam run   # Run the project
gleam test  # Run the tests
gleam run -m benchmark # Run the benchmarks

Implementation#

iv is based on the RRB-Vector, an advanced immutable data structure based on Clojures persistent vectors developed by Bagwell and Rompf. If you're interested in that sort of thing, I highly recommend also checking out L'oranges masters thesis, which is a very rigorous presentation of the algorithms and mathematics behind them. The blog post by Horne-Khan implements the main ideas, but is easier to digest without a strong computer science background.

iv improves on the data structure as presented by offering fast appends, prepends and inserts for arbitrary numbers of elements and improving general node reconstruction time.