Mah
DocsStdlibBlogChangelog
GitHub
Menu
DocsStdlibBlogChangelog GitHub

  • std:math
  • std:random
  • std:collections
  • std:time

  • std:path
  • std:json
  • std:csv
  • std:regex
  • std:bytes
  • std:url

  • std:async
  • std:fs
  • std:process
  • std:thread

  • std:socket
  • std:http

  • std:reflect
  • std:test

Standard library / Basics

std:collections

Three data structures that complement the built-in Vector and Map:

  • Set: distinct values, in the order they were first added.
  • Deque: a double-ended queue, push and pop at both ends in constant time.
  • PriorityQueue: items come out smallest first (a binary heap).

All three work with for, map/filter/reduce and the other iterator methods, and print with their name. They’re usually imported flat:

import "std:collections"

let tags = Set.of(["red", "blue", "red"])
let line = Deque.of(["ana", "bo"])
let jobs = PriorityQueue.of([5, 1, 3])
print(tags, line, jobs.pop())          # Set[red, blue] Deque[ana, bo] 1

Set: distinct values

A Set holds each value once. Values must be usable as Map keys: Strings, Numbers or Bools.

import "std:collections"

let seen = Set.new()
for let word in "the cat and the hat".split(" ") {
    seen.add(word)
}
print(seen, seen.len(), seen.has("cat"))    # Set[the, cat, and, hat] 4 true
print(seen.remove("cat"), seen.remove("dog"))   # true false

Set algebra returns new Sets:

import "std:collections"

let a = Set.of([1, 2, 3, 4])
let b = Set.of([3, 4, 5])
print(a.union(b), a.intersection(b), a.difference(b))   # Set[1, 2, 3, 4, 5] Set[3, 4] Set[1, 2]
print(Set.of([3]).is_subset(a), a.equals(Set.of([4, 3, 2, 1])))   # true true

== on two Sets compares identity, like on Vectors and Maps; use equals to compare contents.

A common use is de-duplicating while keeping the first-seen order: Set.of(items).to_vector().

Deque: a double-ended queue

Vector.push/pop work at the end only; removing from the front of a Vector shifts every item. A Deque does both ends in constant time, which makes it the right structure for queues, sliding windows and breadth-first search:

import "std:collections"

# Breadth-first search over a small graph.
let edges = ["a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []]
let queue = Deque.of(["a"])
let visited = Set.of(["a"])
let order = []
while !queue.is_empty() {
    let node = queue.pop_front()
    order.push(node)
    for let next in edges[node] {
        if !visited.has(next) {
            visited.add(next)
            queue.push_back(next)
        }
    }
}
print(order)                          # [a, b, c, d]

front()/back() peek without removing; get(i) reads any position (negative counts from the back). Popping or peeking an empty Deque gives none, like Vector.pop.

PriorityQueue: smallest first

pop() always gives the smallest item. Items are compared with <, or by a key function you pass to new/of. Equal items come out in the order they were pushed.

import "std:collections"

let tasks = PriorityQueue.new(fn(task) { task.len() })   # shortest first
for let t in ["write docs", "fix", "test it"] {
    tasks.push(t)
}
print(tasks.peek(), tasks.len())                # fix 3
print(tasks.pop(), tasks.pop(), tasks.pop())    # fix test it write docs
print(tasks.pop())                              # none

For largest first, use a key that negates: PriorityQueue.new(fn(x) { 0 - x }). A key can also pick a field, so a queue of structs orders by priority:

import "std:collections"

struct Job { name: String, priority: Number }
let q = PriorityQueue.new(fn(j) { j.priority })
q.push(Job { name: "deploy", priority: 2 })
q.push(Job { name: "hotfix", priority: 1 })
q.push(Job { name: "lunch", priority: 3 })
print(q.to_vector().map(fn(j) { j.name }).reduce())   # [hotfix, deploy, lunch]

Iterating a PriorityQueue (or to_vector()) yields the items smallest first and leaves the queue unchanged.

Reference

Every type has new(), of(values), len(), is_empty(), clear(), to_vector(), and is Iterable and Printable.

Set<T>

Method
add(x)adds x (nothing happens if it’s there)
remove(x)removes x; returns whether it was there
has(x)whether x is in the Set
copy()a new Set with the same values
union(other)values in either Set
intersection(other)values in both
difference(other)values in this Set but not other
is_subset(other)whether every value is also in other
equals(other)the same values, in any order

Deque<T>

Method
push_back(x), push_front(x)add at an end
pop_back(), pop_front()remove and return from an end; none when empty
back(), front()peek at an end; none when empty
get(i)the item i from the front (negative: from the back), none out of range

PriorityQueue<T>

Method
new(key = none), of(values, key = none)an empty / filled queue, ordered by key(item) if given
push(x)adds x
pop()removes and returns the smallest; none when empty
peek()the smallest, left in place; none when empty
Previous std:random Next std:time

Mah — ماه, "moon" in Persian. Built from scratch, pure Python (plus a Rust runtime).

Docs Stdlib Blog Changelog RSS GitHub