Maps and sets

Map<Key, Value> maps keys to values and is the type of the literal ["a": 1]. Set<Item> is a collection without duplicates and has no literal of its own: a list literal builds one wherever a Set is the expected type. Both implementations iterate in the order values were inserted and compare equal regardless of it.

Example#

var ages = ["Ada": 36]
ages["Grace"] = 45
print ages
print ages.keys().toList()

var unique: Set<Int> = [1, 2, 2, 3]
unique.insert 2
print unique

Syntax#

["a": 1, "b": 2]                         the Map literal: TrieMap<String, Int>
[:]                                      the empty Map
map[key]                                 Index.at: panics if the key is absent
map.get(key)                             Index.get: an Option
map[key] = value                         MutableIndex.set

const unique: Set<Int> = [1, 2, 2, 3]    a list literal, adapted because Set is From<Iterate<Item>>
var seen: Set<Int> = []                  the empty Set, and the constant a field of one starts from
Set.of(1, 2, 3)                          from arguments, needs Item: Hash

Rules#

1. A Map has a literal of its own; a Set does not. ["a": 1] is native syntax that builds a TrieMap through Map's own From<Iterate<(Key, Value)>>. A Set is built the way every other target is: a list literal adapts to the type expected of it, so const unique: Set<Int> = [1, 2, 2, 3] is Set.from([1, 2, 2, 3]).

2. Every implementation of Map and Set iterates in insertion order, and removing a value does not reorder the rest. The order reaches the output through Show: an empty Map shows as [:], an empty Set as {} - which is why the order is a rule of the language and not of the implementation.

   A Map iterates as a labelled pair: Map.iterate answers Iterator<(key: Key, value: Value)>, so an entry reads as entry.key and entry.value. A label is not part of the type, so the positional forms mean exactly the same thing and a (Key, Value) pair goes into Map.from unchanged.

   const ages = ["Ada": 36, "Alan": 41]
   print ages.all({ entry => entry.value > 0 })
   for (name, age) in ages {
     print "{name} is {age}"
   }

3. Equality and hashing ignore insertion order, unlike a List. Two maps with the same entries set in a different order are equal and hash the same, because both combine their entries with bitwiseExclusiveOr instead of folding them in sequence.

   const first: Map<String, Int> = ["a": 1, "b": 2]
   const second: Map<String, Int> = ["b": 2, "a": 1]
   print(first == second)

4. The traits ask nothing of Key or Item; only a factory or an implementation that hashes it does. Map.of, Set.of, HashMap, HashSet, TrieMap and TrieSet all need Hash; a hand-written implementation that never hashes its keys would not.

5. A Map's verb for writing a key is set, and its participle is updated rather than setted. remove/ removed follows the usual pattern, and putting one map into another is a for over its entries with set. A Set's in-place verbs are insert/remove/insertAll/removeAll/retainAll, with the participles inserted, insertedAll and removed; its set operations - union, intersection, difference - are nouns and never change either operand. They are functions of the type that take both sets, Set.union(first, second), because neither operand is the one the operation belongs to; insertedAll is the member that fills one set from anything that iterates.

   const ages: Map<String, Int> = ["Ada": 36]
   const older = ages.updated "Ada", 37
   print older
   
   const primes = Set.of 2, 3, 5, 7
   const evenPrimes = Set.intersection primes, Set.of(2, 4, 6)
   print evenPrimes

6. containsKey, keys(), values() and mapValues read a Map without changing it.

7. getOrInsert(key, fallback) reads the value, storing the fallback where there is none, and update changes the stored value in place. The fallback is lazy, so it is only built on a miss - this is what other languages spell entry().or_default(), with the replacement written out because there is no Default trait. What getOrInsert answers is a copy, as every value is, so the grouping loop goes through update:

   var groups: Map<String, List<String>> = [:]
   for name in ["Ada", "Alan", "Grace"] {
     groups.update name.prefix(characters: 1), [] { names => names.append name }
   }
   print groups

8. The empty literals are the constants a field starts from. A field default is a constant (Construction, rule 4), and Set.of() is a call - so an empty Set is [], which the literal builds through Set.from like any other, and an empty Map is [:].

   type Index {
     var seen: Set<String> = []
     var positions: Map<String, Int> = [:]
   }
   
   var index = Index()
   index.seen.insert "Ada"
   index.positions.set "Ada", 1
   print index

What this is not#

Reading map[key] is not the same as map.get(key). The bracket form panics on a missing key, and the message names it: the key "Linus" is not in the map, the key as it shows inside of another value and cut after 60 characters, or the key alone where its type has no Show. Only get answers None.

const ages: Map<String, Int> = ["Ada": 36]
print ages.get("Linus")

const ages: Map<String, Int> = ["Ada": 36]
print ages["Linus"]
// panic: the key "Linus" is not in the map

Related#

• The collection traits - Iterate and Length, which Map and Set are built on.
• Lists - the order-dependent collection Map and Set are compared against.
• Copy and equality - what the generated Equals and Hash do for a field that holds one of these.
• Tuples - the (Key, Value) pair a Map iterates as.