Tzopilotl by Example

16. Persistent Collections

Persistent collections are immutable counterparts to Array and Map, written with a leading #. A persistent vector #[…] is an indexed sequence; a persistent map #[k: v, …] is a keyed collection. They never change in place: an “update” returns a new collection that shares most of its structure with the original, so copies are cheap and the original is always left intact.

They are distinct types from the mutable kinds — just as List is distinct from Array — with no implicit conversion in either direction. The element-update builtins reuse the non-mutating names (push, put, get, remove); there are no ! variants, because there is nothing to mutate.

16.1 Persistent Vectors

-- Literal and type annotation: #[T]
let v = #[1, 2, 3];
v println;                       -- #[1, 2, 3]

-- Indexing is cyclic, like arrays
v[0] println;                    -- 1
v[-1] println;                   -- 3 (last element)
v length println;                -- 3

-- push returns a NEW vector; the original is unchanged
let v2 = v push(4);
v2 println;                      -- #[1, 2, 3, 4]
v println;                       -- #[1, 2, 3]  (untouched)

-- put replaces the element at an index, returning a new vector
let v3 = v put(1, 99);
v3 println;                      -- #[1, 99, 3]

-- Numeric promotion in a literal, like arrays
#[1, 2.0, 3] println;          -- #[1.0, 2.0, 3.0]  (type #[Float])

-- An empty literal takes its element type from the annotation
let e #[Int] = #[];
e length println;                -- 0

-- Equality is structural; $ concatenates
(#[1, 2, 3] == #[1, 2, 3]) println;   -- true
(#[1, 2] $ #[3, 4, 5]) println;        -- #[1, 2, 3, 4, 5]

-- For-loop iteration yields elements
var total = 0;
for (x : v2) { total = total + x; }
total println;                   -- 10

16.2 Persistent Maps

-- Literal and type annotation: #[K:V]
let m = #["x": 1, "y": 2, "z": 3];
m length println;                -- 3

-- Subscript returns Option<V>
m["x"] unwrap println;          -- 1

-- get returns Option<V>; get(key, default) returns V
m get("z") unwrap println;      -- 3
m get("w", 0) println;          -- 0
m contains("x") println;        -- true

-- put and remove return NEW maps; the original is unchanged
let m2 = m put("w", 4);
m2 length println;               -- 4
m contains("w") println;        -- false  (untouched)

let m3 = m2 remove("x");
m3 contains("x") println;       -- false

-- keys and values are persistent vectors
m keys length println;           -- 3
m values length println;         -- 3

-- merge: the right operand's keys win on conflict
let merged = #["a": 1, "b": 2] merge(#["b": 20, "c": 30]);
merged["b"] unwrap println;     -- 20

-- Empty persistent map: #[:]  (element types from the annotation)
let empty #[String:Int] = #[:];
empty length println;            -- 0

-- Equality is structural and order-independent
(#["a": 1, "b": 2] == #["b": 2, "a": 1]) println;  -- true

-- Any hashable key type works (e.g. Int keys)
let im = #[1: "one", 2: "two"];
im[2] unwrap println;            -- "two"

16.3 Conversions

Because the persistent and mutable kinds are distinct types, conversion is explicit and performs a real O(n) build (there is no in-place “freeze”). The four builtins are target-typed:

-- Array <-> persistent vector
let pv = [5, 6, 7] toPersistentVector;
pv toArray println;              -- [5, 6, 7]

-- Map <-> persistent map
let pm = ["x": 1, "y": 2] toPersistentMap;
pm toMap length println;         -- 2

-- The result is independent of later mutation of the source
var src = [1, 2, 3];
let frozen = src toPersistentVector;
src push!(4);
src length println;              -- 4
frozen length println;           -- 3  (unaffected)

16.4 Higher-Order Functions and Auto-mapping

Persistent vectors support the same higher-order and sequence builtins as arrays — map, filter, fold, scan, reverse, take, drop, sort, zip, flatten, and so on — each returning a new persistent vector (or a scalar, for reductions).

let v = #[1, 2, 3, 4];
v map(fn(x Int) { x * 10 }) println;   -- #[10, 20, 30, 40]
v filter(fn(x Int) { x > 2 }) println;  -- #[3, 4]
v fold(0, fn(a Int, x Int) { a + x }) println;  -- 10
v reverse println;                       -- #[4, 3, 2, 1]

Auto-mapping works exactly as it does for arrays: functions expecting a scalar map over a persistent vector, binary operators broadcast and zip, and the @, @@, and cartesian @n forms all apply. The result preserves the persistent-vector kind.

let u = #[1, 2, 3];
(u + 1) println;                     -- #[2, 3, 4]
(u * #[10, 20, 30]) println;          -- #[10, 40, 90]

let dbl = fn(x Int) Int { x * 2 };
u dbl println;                            -- #[2, 4, 6]

-- Deep (@@) auto-mapping over nested persistent vectors, any depth
(#[#[1, 2], #[3, 4]] + 1) println;     -- #[#[2, 3], #[4, 5]]