Docs / Guide / Collections

Collections

Kit provides several collection types for organizing and manipulating data. All collections in Kit are immutable by default, meaning operations return new collections rather than modifying existing ones.

Lists

Lists are ordered, immutable sequences of elements. They are the most commonly used collection type in Kit and support pattern matching.

Creating Lists

# List literals
numbers = [1, 2, 3, 4, 5]
names = ["Alice", "Bob", "Carol"]
empty = []

# Mixed types (with type annotation)
mixed = [1, "two", 3.0]

# Nested lists
matrix = [[1, 2], [3, 4], [5, 6]]

# Range (creates a list)
one-to-ten = List.range 1 10
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Accessing Elements

fruits = ["apple", "banana", "cherry"]

# Get first element
first = head fruits        # => "apple"

# Get remaining elements
rest = tail fruits         # => ["banana", "cherry"]

# Get by index (returns Option)
second = List.nth 1 fruits  # => Some "banana"
missing = List.nth 10 fruits # => None

# Get last element
last = List.last fruits     # => Some "cherry"

# Get length
len = length fruits         # => 3

List Operations

nums = [1, 2, 3]

# Add element to front
with-zero = cons 0 nums      # => [0, 1, 2, 3]

# Concatenate lists
combined = List.concat nums [4, 5]  # => [1, 2, 3, 4, 5]

# Reverse
reversed = List.reverse nums  # => [3, 2, 1]

# Take first n elements
first-two = List.take 2 nums  # => [1, 2]

# Drop first n elements
rest = List.drop 1 nums      # => [2, 3]

# Check if empty
is-empty = List.is-empty? nums   # => false

Transforming Lists

numbers = [1, 2, 3, 4, 5]

# Map - transform each element
doubled = map (fn(x) => x * 2) numbers
# => [2, 4, 6, 8, 10]

# Filter - keep matching elements
evens = filter (fn(x) => x % 2 == 0) numbers
# => [2, 4]

# Fold - reduce to single value
sum = fold (fn(acc, x) => acc + x) 0 numbers
# => 15

# Chained transformations with pipe
result = numbers
  |>> filter (fn(x) => x > 2)
  |>> map (fn(x) => x * x)
  |>> fold (fn(a, x) => a + x) 0
# => 50 (9 + 16 + 25)

Pattern Matching on Lists

describe = fn(list) =>
  match list
    | [] -> "empty list"
    | [x] -> "single element: ${x}"
    | [x, y] -> "two elements: ${x} and ${y}"
    | [head | tail] -> "starts with ${head}, ${length tail} more"

println (describe [])           # => "empty list"
println (describe [1])          # => "single element: 1"
println (describe [1, 2])       # => "two elements: 1 and 2"
println (describe [1, 2, 3])    # => "starts with 1, 2 more"

Records

Records are collections of named fields. They're used for structured data with known field names.

Creating Records

# Record literal
person = {name: "Alice", age: 30, active: true}

# Nested records
user = {
  name: "Bob",
  address: {
    city: "Seattle",
    zip: "98101"
  }
}

# Empty record
empty = {}

Accessing Fields

person = {name: "Alice", age: 30}

# Dot notation
println person.name    # => "Alice"
println person.age     # => 30

# Dynamic access with Record.get
field = "name"
value = Record.get field person  # => Some "Alice"

# Check if field exists
has-name = Record.has-field? "name" person  # => true
has-email = Record.has-field? "email" person # => false

Updating Records

person = {name: "Alice", age: 30}

# Create new record with updated field
older = {person | age: 31}
println older  # => {name: "Alice", age: 31}

# Original is unchanged (immutable)
println person  # => {name: "Alice", age: 30}

# Update multiple fields
updated = {person | age: 31, name: "Alicia"}

# Add new field
with-email = {person | email: "alice@example.com"}

Pattern Matching on Records

greet = fn(person) =>
  match person
    | {name: n, age: a} if a >= 18 -> "Hello, ${n} (adult)"
    | {name: n} -> "Hello, ${n} (minor)"

println (greet {name: "Alice", age: 30})  # => "Hello, Alice (adult)"
println (greet {name: "Bob", age: 15})    # => "Hello, Bob (minor)"

Maps

Maps are key-value collections where keys can be any type. Unlike records, maps support dynamic keys and are useful when keys are not known at compile time.

Creating Maps

# From list of pairs
scores = Map.from-list [("Alice", 95), ("Bob", 87), ("Carol", 92)]

# Empty map
empty = Map.empty

# Build incrementally
map = Map.empty
  |> Map.insert "a" 1
  |> Map.insert "b" 2
  |> Map.insert "c" 3

Map Operations

scores = Map.from-list [("Alice", 95), ("Bob", 87)]

# Get value (returns Option)
alice-score = Map.get "Alice" scores  # => Some 95
missing = Map.get "David" scores      # => None

# Insert or update
updated = Map.insert "Carol" 92 scores

# Delete key
without-bob = Map.delete "Bob" scores

# Check for key
has-alice = Map.has-key? "Alice" scores  # => true

# Get all keys or values
names = Map.keys scores    # => ["Alice", "Bob"]
vals = Map.values scores   # => [95, 87]

# Get size
count = Map.size scores    # => 2

Working with Map Entries

scores = Map.from-list [("Alice", 85), ("Bob", 90)]

# Get entries as list of tuples
entries = Map.entries scores
# => [("Alice", 85), ("Bob", 90)]

# Merge two maps
more-scores = Map.from-list [("Carol", 92)]
all-scores = Map.merge scores more-scores

# Convert to list for transformation
total = Map.values scores |> fold (fn(acc, v) => acc + v) 0
# => 175

Sets

Sets are collections of unique values. They're useful when you need to track membership or eliminate duplicates. 

# Create from list
numbers = Set.from-list [1, 2, 3, 2, 1]  # duplicates removed

# Add element
with-four = Set.insert 4 numbers

# Remove element
without-one = Set.delete 1 numbers

# Check membership
has-two = Set.contains? 2 numbers  # => true

# Set operations
a = Set.from-list [1, 2, 3]
b = Set.from-list [2, 3, 4]

union = Set.union a b          # => {1, 2, 3, 4}
intersection = Set.intersection a b  # => {2, 3}
difference = Set.difference a b      # => {1}

# Convert back to list
list = Set.to-list numbers

Tuples

Tuples are fixed-size collections that can hold elements of different types. They're useful for returning multiple values from a function. 

# Create tuples
pair = ("Alice", 30)
triple = (1, "two", true)

# Access elements
name = Tuple.first pair   # => "Alice"
age = Tuple.second pair   # => 30

# Pattern matching on tuples
describe = fn(tuple) =>
  match tuple
    | (name, age) -> "${name} is ${age} years old"

println (describe ("Alice", 30))
# => "Alice is 30 years old"

# Return multiple values
divide-with-remainder = fn(a, b) =>
  (a / b, a % b)

match divide-with-remainder 17 5
  | (quotient, remainder) ->
      println "17 / 5 = ${quotient} remainder ${remainder}"
# => "17 / 5 = 3 remainder 2"

Extended Collections

For specialized data structures beyond the core collections, Kit's standard library includes the Container module which provides:

  • Deque - Double-ended queue with O(1) push/pop at both ends
  • Heap - Priority queue / min-heap
  • Queue - FIFO queue
  • LinkedList - Singly-linked list
  • Trie - Prefix tree for string keys
  • Zipper - Functional cursor for efficient traversal and editing
  • SkipList - Probabilistic sorted list with O(log n) operations
  • Bloom - Bloom filter for probabilistic membership testing
  • BinaryTree, AVLTree, RBTree, BTree - Various tree structures
  • MerkleTree - Hash tree for data integrity verification

Persistent Data Structures

For persistent immutable data structures with structural sharing, use the Persistent module. It provides Clojure-inspired structures that preserve previous versions when modified, ideal for undo/redo, event sourcing, and concurrent access:

  • PVec - Persistent vector with efficient random access and updates
  • PMap - Persistent hash map with structural sharing
  • PSet - Persistent set built on PMap
# Persistent vectors share structure
v1 = PVec.from-list [1, 2, 3]
v2 = PVec.append 4 v1    # v1 unchanged, v2 shares most of v1's memory

# Persistent maps
m1 = PMap.from-list [("a", 1), ("b", 2)]
m2 = PMap.insert "c" 3 m1  # m1 unchanged

Choosing a Collection

Collection Use When Key Features
List Ordered sequence of same-type elements Pattern matching, map/filter/fold, efficient prepend
Record Fixed structure with named fields Dot access, type-safe fields, update syntax
Map Dynamic key-value pairs Any key type, dynamic keys, lookup by key
Set Unique values, membership tests Fast lookup, union/intersection, no duplicates
Tuple Fixed-size mixed types Multiple return values, lightweight grouping
Container.* Specialized data structures Deque, Heap, Queue, Trie, Trees, Bloom filters
PVec/PMap/PSet Undo/redo, event sourcing, concurrent access Structural sharing, preserves old versions