Home / Docs / Standard library
Maps
Status: Normative, v0.2 (ADR 0069).
Map[K, V] is a built-in keyed collection: a finite set of keys, each mapped to one value, ordered by its keys. Maps are values, as lists are (spec/17).
Editions. The constructs of this chapter exist only in packages of edition 0.2 and later (spec/13 §7). In edition 0.1, Map, Entry and empty_map are ordinary names.
1. The type
- Built-in.
Map[K, V]is a built-in type with two type arguments. A user kind namedMaporEntryis U1002, as forI8(spec/18 §1). - Keys.
KMUST satisfyOrd(spec/20 §1):Int,I8toU64,Text, or a sum whose variants have no payload. A key type that does not is U2025, where the type is written or instantiated. In a generic function,Map[T, V]needsT: Ord, written or inferred (spec/20 §3 rule 4). - Order. A map's entries are ordered by their keys, ascending, by the order of spec/03 §1 and spec/20 §5. Every operation that lists them uses that order.
- Entries. The prelude declares
kind Entry[K, V]with the fieldskey: Kandvalue: V. - Equality.
==on maps is structural: the same keys, each with an equal value.Map[K, V]satisfiesEqwhenVdoes, and neverOrd(spec/20 §1). - Refinements. A map type may be refined, as
kind Counts = Map[Text, Int] where it.len > 0.
2. Operations
The operations are a prelude function and built-in methods resolved by the receiver, as the conversions of spec/18 §4 are. They are not user overloading (charter §6). Every argument after the receiver is labeled.
| Operation | Type | Contract |
|---|---|---|
empty_map() |
Map[K, V], from the expected type |
ensures result.len == 0 |
m.len |
Int |
m.len >= 0 holds of every map |
m.has(key: k) |
Bool |
none beyond §5 |
m.get(key: k) |
Option[V] |
result is Some exactly when m.has(key: k) |
edit m.set(key: k, value: v) |
Unit |
ensures m.has(key: k) and m.get(key: k) == Some(v); m.len == old(m).len when old(m).has(key: k), else old(m).len + 1 |
edit m.remove(key: k) |
Unit |
ensures not m.has(key: k); m.len == old(m).len - 1 when old(m).has(key: k), else old(m).len |
m.with(key: k, value: v) |
Map[K, V] |
the contract of set, for the result |
m.without(key: k) |
Map[K, V] |
the contract of remove, for the result |
m.keys() |
List[K] |
ensures result.len == m.len |
m.values() |
List[V] |
ensures result.len == m.len |
m.entries() |
List[Entry[K, V]] |
ensures result.len == m.len |
edit m.update(key: k, initial: i, change: f) |
Unit |
edition 0.5 (rule 5): sets k to f(v), where v is the value of k, or i when m has no k; the contract of set at k |
-
Updates.
setandremovetake the receiver asedit, and follow spec/17 §3: the receiver is a place, the call is the whole expression of its statement, andold(m)in the table is the receiver's value before the call.- (v0.3, ADR 0103.) With a refined key or value type,
withandsetstore theirkeyandvalueat those types, with an obligation each (spec/12 §3).has,get,removeandwithouttake the key at the base of the key type: a lookup stores nothing, so a key outside the refinement finds no entry.
- (v0.3, ADR 0103.) With a refined key or value type,
-
Absence is not a failure.
getreturnsNonefor a missing key. Handle it withif none(spec/06 §3) orwhen. -
Iteration.
keys,valuesandentrieslist the entries in key order, so aforover them visits the keys in ascending order. -
Interpolation (ADR 0068). A map renders as
{k: v, …}in key order, with keys and values in the Una form of spec/11 §5, and{}when it is empty:{"a": 1, "b": 2}. -
update(v0.5, ADR 0119 rule 18, the amendment of ADR 0069; ADR 0139 moved it from edition0.4). In edition0.5,edit m.update(key: k, initial: i, change: f)changes a value in one statement:- It takes the receiver as
edit, assetdoes (rule 1), and its contract is that ofsetatk, withf(v)for the value. initialhas the map's value typeV, as the parameter and result ofchangedo: the type comes from the map, soinitial: []for aMap[Text, List[Text]]is an emptyList[Text].changehas the typefn(V) -> V.updatedeclaresuses of changeandfails of change, asmapdoes (spec/14 §1, ADR 0062), and callschangeexactly once. Whenchangefails, the call fails with it andmkeeps its value from before the call (spec/17 §7 rule 1).- It is a built-in method, reached only by method syntax on a map: it resolves ahead of any function named
updatein scope, and no nameupdateenters scope. A package function namedupdatewhose first parameter is aMap, refined or not, or a type parameter, is U1002 at its declaration in edition0.5, and so is an import of one (spec/28 §2). - Its cost is O(log n): a lookup and an insertion (
§5). - Labels.
changeruns under the program counter of the call joined with the map's top label, the labels of its key position and those ofk, since whether it receives the stored value oridepends on whethermholdsk(ADR 0119 IF7). Its result flows into the value position, andkinto the key position, as forset(§3).
unafor word in words edit counts.update(key: word, initial: 0, change: fn(n) -> n + 1) - It takes the receiver as
3. Information flow
- The keys are part of the shape. The label of the key position of a map's type is below the map's top label: a
Map[secret Text, Int]has asecrettop label, written or not. Which keys are equal decides the size of a map and which keys it holds. - Reads.
m.len,m.has(key: k), and the top ofm.get(key: k)carry the top label ofmjoined with every label ofk. The payload ofSomecarries the labels of the value position. - Listing.
keys(),values()andentries()carry the top label ofm, and their elements carry the labels of the key and value positions. - Updates.
set,remove,withandwithoutraise the map's top label by every label of the key, and its value position by every label of the value. An editable binding keeps its declared labels (spec/17 §6 rule 1), so asetwith a key above the map's top label is U4001 at the key. - Generic code. In a generic body, a key of a type parameter
T: Ordcarriesℓ*_T(spec/07 §7 rule 8).
4. Verification
- Sorts. Each instantiation
Map[K, V]is one sort,i!Map_<K>_<V>, mangled asListis (spec/12 §4). - Functions.
len : Map → Int,has : Map × K → Boolandget : Map × K → Option[V]are uninterpreted.len(m) ≥ 0is a ground fact for every map term. - Contracts. Each operation's contract in §2 is a hypothesis after the call, and
empty_map()giveslen = 0. In editions0.2to0.4,setandremovegive no fact about other keys. (v0.5, ADR 0069 amendment of 2026-10-19, moved with ADR 0119 by ADR 0139.) In edition0.5,set,remove,with,withoutandupdateat the keyxkeephasandgetat every other key termyof the query, guarded byy != x, asspec/28 §11rule 3 states. - The refinement language (spec/03 §3) gains
m.lenandm.has(key: k)on a map term, so they may appear inrequires,ensures,whereand predicates.
5. Dynamic semantics
- Values. A map is a value.
setandremovegive the binding a new map, and every other binding that held the old one keeps it. - Representation. The interpreter and the native runtime keep a map in Rust's standard ordered map (
std::collections::BTreeMap) over the keys' order: O(log n) per lookup, insertion and removal. A native update happens in place when the map is uniquely held, and on a copy otherwise (spec/16 §4 rule 7). Nothing of this is observable. - Equivalence. Both engines list entries in the same order, so the output and the trace of a program agree (spec/16 §5). A map in the trace renders as in §2 rule 4.