coal-containers

A collection of functional data structures for the Coal programming language, providing efficient implementations of common container types.

Overview

coal-containers includes four essential data structures for functional programming in Coal:

• Map — An AVL tree-based associative map with automatic balancing
• Set — A set implementation built on top of Map
• Tree — General-purpose tree structure (rose tree) with arbitrary children
• NonEmpty.List — Type-safe non-empty list with guaranteed head element

Features

Map

An efficient key-value store implemented as a self-balancing AVL tree, ensuring O(log n) performance for insertions, deletions, and lookups.

Key operations:

• empty — Create an empty map
• singleton(key, val) — Create a map with a single key-value pair
• insert(key, val, map) — Insert or update a key-value pair
• delete(key, map) — Remove a key from the map
• lookup(key, map) — Find a value by key (returns Option<val>)
• is_empty(map) — Check if map is empty
• size(map) — Get the number of entries

Example:

import Containers.Map(empty, insert, lookup)
let map = empty
 |. insert(1, "one")
 |. insert(2, "two")
 |. insert(3, "three")
let test = lookup(2, map) // Some("two")

Set

A set collection for storing unique elements, implemented using Map internally.

Key operations:

• empty — Create an empty set
• singleton(element) — Create a set with one element
• insert(element, set) — Add an element
• delete(element, set) — Remove an element
• is_member(element, set) — Check if element exists
• union(set1, set2) — Combine two sets
• intersection(set1, set2) — Find common elements
• map(f, set) — Transform all elements
• filter(predicate, set) — Keep elements matching predicate
• to_list(set) / from_list(list) — Convert between sets and lists

Example:

import Containers.Set(empty, insert, union, is_member)
let numbers = empty
 |. insert(1)
 |. insert(2)
 |. insert(3)
let moreNumbers = empty
 |. insert(3)
 |. insert(4)
let combined = union(numbers, moreNumbers)
let test = is_member(4, combined) // true

Tree

A general-purpose tree structure where each node can have an arbitrary number of children (also known as a rose tree or multi-way tree).

Key operations:

• leaf(value) — Create a leaf node
• node(value, children) — Create a node with children
• size(tree) — Count total nodes
• height(tree) — Calculate tree height
• tree_map(f, tree) — Apply function to all values

Example:

import Containers.Tree(leaf, node)
let tree = node("root", [
 leaf("child1"),
 node("child2", [
 leaf("grandchild1"),
 leaf("grandchild2")
 ]),
 leaf("child3")
])

NonEmpty.List

A list type that guarantees at least one element at compile time, eliminating the need for runtime checks when you know a list will never be empty.

Key operations:

• Cons(head, tail) — Constructor
• singleton(elem) — Create a single-element list
• head(list) — Get first element (always safe!)
• tail(list) — Get remaining elements
• uncons(list) — Extract head and tail as tuple
• map(f, list) — Transform all elements
• append(list1, list2) — Concatenate two non-empty lists
• reverse(list) — Reverse the list
• to_list(list) / from_list(list) — Convert to/from regular lists

Example:

import Containers.NonEmpty.List(Cons, head, map)
let numbers = Cons(1, [2, 3, 4, 5])
let first = head(numbers) // 1 (no Option needed!)
let doubled = map(fn(x) => x * 2, numbers)
// Cons(2, [4, 6, 8, 10])

Installation

Add coal-containers as a dependency in your coal.json file:

{
 "dependencies": {
 "coal-containers": {
 "version": "*",
 "git": "ssh://git@codeberg.org/laserpants/coal-containers.git"
 }
 }
}

Usage

Import the modules you need in your Coal source files:

// Import specific functions
import Containers.Map(empty, insert, lookup)
import Containers.Set(singleton, union)
// Import entire namespace
import namespace Containers.Tree
// Import types and functions
import Containers.NonEmpty.List(NonEmptyList, Cons, head, tail)

Testing

The project includes tests for all data structures. Tests are written using the coal-micro-test framework.

Test files are located in the test/Containers/ directory, mirroring the source structure.

Project structure

coal-containers/
├── src/
│ └── Containers/
│ ├── Map.coal # AVL tree-based map
│ ├── Set.coal # Set implementation
│ ├── Tree.coal # General tree (rose tree)
│ └── NonEmpty/
│ └── List.coal # Non-empty list
├── test/
│ ├── Main.coal
│ └── Containers/
│ ├── MapSpec.coal
│ ├── SetSpec.coal
│ ├── TreeSpec.coal
│ └── NonEmpty/
│ └── ListSpec.coal
├── coal.json # Project configuration
└── README.md

Performance characteristics

*Map and Tree size operations use fold-based computations

Implementation details

AVL tree balancing

The Map implementation uses AVL tree rotations to maintain balance after insertions and deletions, ensuring logarithmic time complexity for operations. The tree tracks height at each node and performs left and right rotations when the balance factor exceeds ±1.

Set implementation

Set is implemented as a wrapper around Map, storing elements as keys with unit values. This allows Set to leverage all of Map's balancing and performance characteristics.

Contributing

Contributions are welcome! Please ensure that:

• All new features include corresponding test cases
• Code follows the existing style and conventions
• Tests pass before submitting changes

License

This project is licensed under the MIT License. See LICENSE for details.

Author

Copyright (c) 2025–present Heikki Johannes Hildén