Docs / Standard Library / Container

Container

The Container module provides advanced data structures beyond the core List, Map, and Set types. Includes queues, stacks, heaps, trees, tries, and specialized structures like bloom filters.

Immutable by Default

All container operations return new structures rather than modifying in place, following Kit's functional programming principles.

Deque

Double-ended queue supporting efficient insertion and removal at both ends.

Deque.empty
Deque a
Creates an empty deque.
Deque.push-front
a -> Deque a -> Deque a
Adds an element to the front of the deque.
deque = Deque.empty |> Deque.push-front 1 |> Deque.push-front 2
# deque contains [2, 1]
Deque.push-back
a -> Deque a -> Deque a
Adds an element to the back of the deque.
Deque.pop-front / Deque.pop-back
Deque a -> Option a
Removes and returns element from front/back. Returns None if empty.
Deque.peek-front / Deque.peek-back
Deque a -> Option a
Returns element without removing it.
Deque.size / Deque.is-empty? / Deque.to-list / Deque.from-list
Standard container operations.

Heap

Min-heap (priority queue) that always provides access to the smallest element.

Heap.empty
Heap a
Creates an empty min-heap.
Heap.push
a -> Heap a -> Heap a
Adds an element to the heap, maintaining heap property.
heap = Heap.empty |> Heap.push 5 |> Heap.push 3 |> Heap.push 7
Heap.peek heap  # => Some 3 (smallest)
Heap.pop
Heap a -> Option a
Removes and returns the smallest element.
Heap.peek
Heap a -> Option a
Returns the smallest element without removing it.

Queue

FIFO (first-in, first-out) queue.

Queue.enqueue
a -> Queue a -> Queue a
Adds element to the back of the queue.
Queue.dequeue
Queue a -> Option a
Removes and returns the front element.
q = Queue.empty |> Queue.enqueue "first" |> Queue.enqueue "second"
Queue.dequeue q  # => Some "first"

LinkedList

Singly-linked list with efficient prepend operations.

LinkedList.prepend
a -> LinkedList a -> LinkedList a
Adds element to the front (O(1)).
LinkedList.head / LinkedList.tail
LinkedList a -> Option a / Option (LinkedList a)
Get first element or rest of list.
LinkedList.nth
Int -> LinkedList a -> Option a
Get element at index (O(n)).

Trie

Prefix tree for efficient string key operations and prefix matching.

Trie.insert
String -> Trie -> Trie
Insert a key into the trie.
Trie.contains? / Trie.starts-with?
String -> Trie -> Bool
Check for exact key or prefix match.
trie = Trie.empty |> Trie.insert "hello" |> Trie.insert "help"
Trie.starts-with? "hel" trie  # => true
Trie.keys-with-prefix
String -> Trie -> [String]
Get all keys starting with given prefix.

Zipper

List with a movable cursor for efficient local updates.

Zipper.from-list
[a] -> Zipper a
Create zipper with cursor at start.
Zipper.left / Zipper.right
Zipper a -> Option (Zipper a)
Move cursor left or right.
Zipper.current / Zipper.insert / Zipper.delete / Zipper.replace
Get, insert, delete, or replace element at cursor.

SkipList

Probabilistic sorted data structure with O(log n) operations.

SkipList.insert / SkipList.contains? / SkipList.remove
a -> SkipList a -> SkipList a / Bool
Standard sorted set operations.
SkipList.range
a -> a -> SkipList a -> [a]
Get all elements in the given range.

Bloom

Probabilistic set for fast membership testing (may have false positives).

Bloom.create
Int -> Int -> Bloom
Create filter with bit array size and number of hash functions.
# 1000-bit filter with 3 hash functions
filter = Bloom.create 1000 3
Bloom.add / Bloom.contains?
a -> Bloom -> Bloom / Bool
Add element or test membership. contains? may return false positives but never false negatives.

BinaryTree

Simple binary search tree (unbalanced).

BinaryTree.insert / BinaryTree.contains? / BinaryTree.delete
a -> BinaryTree a -> BinaryTree a / Bool
Standard BST operations.
tree = BinaryTree.empty
  |> BinaryTree.insert 5
  |> BinaryTree.insert 3
  |> BinaryTree.insert 7
BinaryTree.to-list tree  # => [3, 5, 7]
BinaryTree.min / BinaryTree.max
BinaryTree a -> Option a
Get minimum or maximum value.

AVLTree

Self-balancing binary search tree with guaranteed O(log n) operations.

AVLTree.insert / AVLTree.delete
a -> AVLTree a -> AVLTree a
Insert or delete while maintaining balance.
AVLTree.height / AVLTree.is-balanced?
AVLTree a -> Int / Bool
Get tree height or verify balance invariant.

RBTree

Red-black tree with guaranteed O(log n) operations.

RBTree.insert / RBTree.contains? / RBTree.find-min / RBTree.find-max
Standard balanced tree operations.

BTree

B-tree optimized for disk-based storage with high branching factor.

BTree.insert / BTree.contains? / BTree.find-min / BTree.find-max
Standard B-tree operations.

MerkleTree

Hash tree for data integrity verification.

MerkleTree.from-list
[a] -> MerkleTree a
Build Merkle tree from list of values.
MerkleTree.root-hash
MerkleTree a -> Option String
Get the root hash (SHA-256 in hex).
tree = MerkleTree.from-list ["a", "b", "c", "d"]
MerkleTree.root-hash tree  # => Some "58c89d..."
MerkleTree.proof / MerkleTree.verify
a -> MerkleTree a -> Option [a] / [a] -> String -> Bool
Generate inclusion proof and verify against root hash.