Maps
Release v0.4.0
Map[K, V] maps keys to values, in ascending key order (spec/21). It is a value, as a list is.
- Keys satisfy
Ord:Int, the fixed-width types,Text, or a sum whose variants have no payload. Any other key type is U2025, and a public generic function writes[K: Ord]. empty_map()takes its type from its context, as[]does:let edit m: Map[Text, Int] = empty_map().- Reads:
m.len,m.has(key: k),m.get(key: k), which isNonefor a missing key and is handled withif none, andm.keys(),m.values()andm.entries(), lists in key order. AnEntryhas the fieldskeyandvalue. - Updates:
edit m.set(key: k, value: v)andedit m.remove(key: k)on an editable binding, each the whole statement.m.with(key: k, value: v)andm.without(key: k)give a new map instead. - Cost:
lenis O(1);get,has,setandremoveare O(log n), in place when nothing else holds the map;withandwithouton a map another binding still holds copy it, O(n). - Proofs:
m.lenandm.has(key: k)may appear in contracts andwhereclauses. Afterset, the key is present with its value; afterremove, it is absent. Nothing is known of the other keys. - Labels: which keys a map holds is part of its shape, so
len,has,getand the listings carry the labels of the keys with the map's top label. Setting asecretkey in a map whose top label is public is U4001 at the key: declare itsecret Map[Text, Int]. - Type arguments are never refined: a refined kind such as
Nat, orInt in 0..5, cannot instantiate a type parameter, soMap[Text, Nat]andList[Nat]are U2002, as is any generic kind given one. Write the base type,Map[Text, Int], and refine where a value is used: a function that returns a count as-> Natchecks it there, for instance withif n >= 0 then n else 0. The values a map holds are then anyInt, so a contract about them needs that check too. - A map prints as
{"a": 1, "b": 2}, and{}when empty.
una
module words
--- How often each word occurs.
pub counts(words: List[Text]) -> Map[Text, Int]
=
let edit counts: Map[Text, Int] = empty_map()
for word in words
let n = counts.get(key: word)
if none use 0
edit counts.set(key: word, value: n + 1)
counts
--- The words seen at least `least` times, in ascending order.
pub frequent(counts: Map[Text, Int], least: Int) -> List[Text]
=
let kept = counts.entries().filter(keep: fn(e) -> e.value >= least)
kept.map(each: fn(e) -> e.key)
--- The count of a word the map has.
pub count_of(counts: Map[Text, Int], word: Text) -> Int
requires counts.has(key: word)
=
let n = counts.get(key: word)
if none use 0
nuna
-- fails with U2002
module demo
pub empty_counts() -> Map[Text, Nat] = empty_map()