Home / Learn / 10 Collections
10.4 Maps
Page 5 of 11
10.4.1 What a map is
A map holds values under keys. Think of a stock ledger: each SKU has one line, and the line says how many units are on hand. You never read the ledger from the top to find a SKU; you go to its line. A map works the same way. Each key, here a SKU, appears once, and leads to one value, here the units. A key together with its value is an entry.
Map[K, V] is the type of a map whose keys have the type K and whose values have the type V. The stock of each SKU is a Map[Text, Int]. The units sold in each category are a Map[Text, Int] too, and the summary of each category, in the day-to-day program, a Map[Text, Summary].
10.4.2 Why a program needs maps
Count the units sold in each category with what this chapter has shown so far: a list of the categories, and a filter and a sum for each one.
module sales
--- A sale of some units of one SKU, in a category.
kind Sale
sku: Text
category: Text
quantity: Int
--- The units sold in one category: a walk over every sale, for each category asked.
units_of(sales: List[Sale], category: Text) -> Int = sales.filter(keep: fn(sale) -> sale.category == category).map(each: fn(sale) -> sale.quantity).sum()
pub main() -> Unit
uses @console: Console[print]
=
let lamp = Sale(sku: "LAMP-01", category: "lighting", quantity: 2)
let rug = Sale(sku: "RUG-07", category: "textiles", quantity: 1)
let shade = Sale(sku: "SHADE-05", category: "lighting", quantity: 3)
let spade = Sale(sku: "SPADE-02", category: "garden", quantity: 4)
let sales = [lamp, rug, shade, spade]
let categories = ["lighting", "textiles"]
for category in categories
@console.print("{category}: {units_of(sales, category: category)}")
@console.print("{sales.map(each: fn(sale) -> sale.quantity).sum()} units sold in all")una run . prints:
lighting: 5
textiles: 1
10 units sold in allThe totals by category add up to 6, and the store sold 10 units. The 4 units of SPADE-02 are lost, because nobody wrote "garden" into the list of categories. The code has to know every category in advance. It is also slow on a real day: it walks every sale once for each category, so 1,000 sales in 50 categories take 50,000 tests. A map fixes both. You add each sale to its category's entry as you meet it, so a new category gets an entry by itself, and each sale is visited once.
10.4.3 How to write and use a map
The step of this part keeps a ledger. Its main prints one line per group of operations:
--- The units on hand of each SKU, after a delivery and a sale.
stock_after_day() -> Map[Text, Int]
=
let edit stock: Map[Text, Int] = empty_map()
edit stock.set(key: "LAMP-01", value: 4)
edit stock.set(key: "DESK-02", value: 1)
edit stock.set(key: "VASE-03", value: 6)
edit stock.set(key: "LAMP-01", value: 3)
edit stock.remove(key: "VASE-03")
stock10.4.3.1 An empty map: empty_map()
A map starts empty. empty_map() makes one, and takes its key and value types from the name it is given to, so write them there: let edit stock: Map[Text, Int] = empty_map().
let empty: Map[Text, Int] = empty_map()
let stock = stock_after_day()
@console.print("{empty} {empty.len} / {stock} {stock.len}"){} 0 / {"DESK-02": 1, "LAMP-01": 3} 2A map in an interpolation is written between braces, {} when empty, and m.len is its number of entries. stock_after_day set LAMP-01 twice and removed VASE-03, so two entries are left.
10.4.3.2 Changing a map in place: edit m.set and edit m.remove
edit stock.set(key: "LAMP-01", value: 4) adds the key with its value, or replaces the value when the key is already there. edit stock.remove(key: "VASE-03") takes the key out. Both change the map in place, so:
- the name is declared
let edit, since only an editable name may change (section 9.2); - the call starts with the word
edit, which marks the line where the map changes, as for a list'sset(section 16.2 explainseditat a call); - the call stands alone on its line, as a step: it gives no value.
In stock_after_day, the fourth line sets LAMP-01 again, to 3, so the map keeps one entry for it.
10.4.3.3 A new map from an old one: with and without
stock.with(key: "RUG-07", value: 9) gives a new map with one more entry, or one changed entry, and without a new map with one key fewer. The map you call them on does not change, so they need no edit:
let restocked = stock.with(key: "RUG-07", value: 9)
let retired = restocked.without(key: "DESK-02")
@console.print("{restocked} {retired} {stock}"){"DESK-02": 1, "LAMP-01": 3, "RUG-07": 9} {"LAMP-01": 3, "RUG-07": 9} {"DESK-02": 1, "LAMP-01": 3}The last of the three maps is stock, unchanged.
10.4.3.4 Reading: get and has
get gives an Option: Some with the value, or None for a key the map does not hold. has answers only whether the key is there.
let lamps = stock.get(key: "LAMP-01")
let vases = stock.get(key: "VASE-03")
let has_desks = stock.has(key: "DESK-02")
let has_vases = stock.has(key: "VASE-03")
@console.print("{lamps} {vases} {has_desks} {has_vases}")Some(3) None true false10.4.3.5 Listing: keys, values and entries
keys() and values() give lists, and entries() a list of Entry records, each with the fields key and value. A for loop over entries() visits each key with its value:
@console.print("{restocked.keys()} {restocked.values()}")
for entry in restocked.entries()
@console.print("{entry.key} has {entry.value}")["DESK-02", "LAMP-01", "RUG-07"] [1, 3, 9]
DESK-02 has 1
LAMP-01 has 3
RUG-07 has 910.4.4 Stock by SKU
The forms together. The step keeps the stock of each SKU, and groups sales by category:
module stock
--- A sale of some units of one SKU, in a category.
kind Sale
sku: Text
category: Text
quantity: Int
pub main() -> Unit
uses @console: Console[print]
=
let edit stock: Map[Text, Int] = empty_map()
edit stock.set(key: "LAMP-01", value: 4)
edit stock.set(key: "DESK-02", value: 1)
let restocked = stock.with(key: "RUG-07", value: 9)
@console.print("{stock} and {restocked}")
let lamps_left = stock.get(key: "LAMP-01")
let vases_left = stock.get(key: "VASE-03")
@console.print("{lamps_left} {vases_left}")
@console.print("{restocked.keys()}")
let lamp = Sale(sku: "LAMP-01", category: "lighting", quantity: 2)
let rug = Sale(sku: "RUG-07", category: "textiles", quantity: 1)
let shade = Sale(sku: "SHADE-05", category: "lighting", quantity: 3)
for entry in units_by_category([lamp, rug, shade]).entries()
@console.print("{entry.key}: {entry.value}")
--- How many units each category sold.
units_by_category(sales: List[Sale]) -> Map[Text, Int]
=
let edit totals: Map[Text, Int] = empty_map()
for sale in sales
let before = totals.get(key: sale.category).or_else(default: 0)
edit totals.set(key: sale.category, value: before + sale.quantity)
totalslet edit stock: Map[Text, Int] = empty_map(). An empty map, with its key and value types written.edit stock.set(key: "LAMP-01", value: 4).setadds the key, or replaces its value. It changes the map, so the name islet edit, and the call starts withedit.stock.with(key: "RUG-07", value: 9). The value form: a new map with one more entry.stockkeeps its two entries, as the first line of the output shows.stock.get(key: "VASE-03").getgives anOption:Nonefor a key the map does not hold. A missing key is not an error.totals.get(key: sale.category).or_else(default: 0). The grouping pattern: read the total so far, with0for a category not seen yet, thensetthe new total. You will meet it again in the day-to-day program.
una run . prints:
{"DESK-02": 1, "LAMP-01": 4} and {"DESK-02": 1, "LAMP-01": 4, "RUG-07": 9}
Some(4) None
["DESK-02", "LAMP-01", "RUG-07"]
lighting: 5
textiles: 1units_by_category needs no list of categories. The first sale of a category finds no entry, starts from 0, and creates one; every later sale of it adds to that entry.
10.4.5 How a map behaves
10.4.5.1 Entries in key order
A map keeps its entries ordered by key, from the smallest up, not in the order you added them. keys(), values() and entries() all list them in that order, and so does interpolation. Texts order character by character, and numbers by value:
let aisles = empty_map().with(key: 12, value: "garden").with(key: 3, value: "lighting")
@console.print("{aisles}"){3: "lighting", 12: "garden"}The key 12 was added first, and 3 still comes first. So a report built from a map comes out sorted by key, with no sort call, and the same input always gives the same output.
10.4.5.2 One value per key
A key appears once. set and with on a key that is there replace its value, so the length stays the same. To keep several values under one key, make the value a list, as Map[Int, List[Text]] in exercise 3.
10.4.5.3 A missing key is not an error
get on a missing key gives None, and remove or without on a missing key leaves the map as it is. Neither stops the program.
10.4.5.4 Maps are values, and compare by content
with and without never change the map they are called on, and set and remove change only the name they are written on. Two maps are equal when they hold the same keys with equal values:
let same = restocked.without(key: "DESK-02")
@console.print("{retired == same} {retired == stock}")true false10.4.5.5 Keys need an order
A key type must have an order, the constraint Ord: Text, Int, the fixed-width integers, or a sum kind whose variants carry no data. A record has no order, so it cannot be a key. Key a map by sales, and the checker refuses:
--- a/src/stock.una
+++ b/src/stock.una
@@ -12,2 +12,3 @@
let edit stock: Map[Text, Int] = empty_map()
+ let edit by_sale: Map[Sale, Int] = empty_map()
edit stock.set(key: "LAMP-01", value: 4)[U2025] Error: a map's key type must satisfy `Ord`, and `Sale` does not
╭─[ src/stock.una:13:21 ]
│
13 │ let edit by_sale: Map[Sale, Int] = empty_map()
│ ───────┬──────
│ ╰──────── a map's key type must satisfy `Ord`, and `Sale` does not
│
│ Note: run `una explain U2025` for an explanationThe message says that the key type must satisfy Ord, the constraint of types with an order (section 4.4), and that Sale does not. A second message, at empty_map(), says the same thing about the map it would make. Key the map by a field that has an order instead, such as the SKU.
10.4.5.6 Cost
Each lookup, insertion and removal takes time in proportion to the logarithm of the number of entries, written O(log n). The time grows very slowly with the size of the map: a map of a million entries takes about twice the steps of a map of a thousand, where first_where on a list may look at every element.
10.4.6 The operations of a map
| Operation | Gives | Notes |
|---|---|---|
empty_map() |
a new map | its types come from where it is used |
m.len |
Int |
the number of entries |
m.has(key: k) |
Bool |
|
m.get(key: k) |
Option[V] |
None for a missing key |
edit m.set(key: k, value: v) |
changes m |
adds or replaces |
edit m.remove(key: k) |
changes m |
|
m.with(key: k, value: v) |
a new map | m is unchanged |
m.without(key: k) |
a new map | m is unchanged |
m.keys(), m.values(), m.entries() |
lists | in key order |
10.4.7 A map or a list
Which to use:
| You want to… | Use |
|---|---|
| Values in the order they arrived, repeats allowed | a list |
| One value per key, found by its key | a map |
| Totals or groups by a key you meet as you go | a map, with get, or_else and set |
| Output sorted by a key, every time | a map keyed by it |
| Values sorted by something a record holds | a map keyed by that field, then values() |
Edition 0.2 has the list and the map, which cover the programs of this book. Edition 0.5, a preview, adds queues, stacks and sets in the module std.collections.
10.4.8 Check yourself: maps
Predict what these two lines print:
let tally = empty_map().with(key: "RUG-07", value: 1).with(key: "LAMP-01", value: 2).with(key: "RUG-07", value: 5)
@console.print("{tally} {tally.len}")Show the answer
{"LAMP-01": 2, "RUG-07": 5} 2The second with on RUG-07 replaces its value, so the map has two entries, not three, and RUG-07 holds 5. The keys print in order, LAMP-01 first, whatever order they were added in.
Next:10.5 JSON