Home / Learn / 10 Collections

Release v0.4.0Edition 0.2

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.

steps/17-groups-by-hand/src/sales.unacheckrununa
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:

Output
lighting: 5
textiles: 1
10 units sold in all

The 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:

steps/18-map-forms/src/ledger.unauna
--- 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")
  stock

10.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().

steps/18-map-forms/src/ledger.unauna
  let empty: Map[Text, Int] = empty_map()
  let stock = stock_after_day()
  @console.print("{empty} {empty.len} / {stock} {stock.len}")
Output
{} 0 / {"DESK-02": 1, "LAMP-01": 3} 2

A 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:

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:

steps/18-map-forms/src/ledger.unauna
  let restocked = stock.with(key: "RUG-07", value: 9)
  let retired = restocked.without(key: "DESK-02")
  @console.print("{restocked} {retired} {stock}")
Output
{"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.

steps/18-map-forms/src/ledger.unauna
  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}")
Output
Some(3) None true false

10.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:

steps/18-map-forms/src/ledger.unauna
  @console.print("{restocked.keys()} {restocked.values()}")
  for entry in restocked.entries()
    @console.print("{entry.key} has {entry.value}")
Output
["DESK-02", "LAMP-01", "RUG-07"] [1, 3, 9]
DESK-02 has 1
LAMP-01 has 3
RUG-07 has 9

10.4.4 Stock by SKU

The forms together. The step keeps the stock of each SKU, and groups sales by category:

steps/19-maps/src/stock.unacheckrununa
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)
  totals
  1. let edit stock: Map[Text, Int] = empty_map(). An empty map, with its key and value types written.
  2. edit stock.set(key: "LAMP-01", value: 4). set adds the key, or replaces its value. It changes the map, so the name is let edit, and the call starts with edit.
  3. stock.with(key: "RUG-07", value: 9). The value form: a new map with one more entry. stock keeps its two entries, as the first line of the output shows.
  4. stock.get(key: "VASE-03"). get gives an Option: None for a key the map does not hold. A missing key is not an error.
  5. totals.get(key: sale.category).or_else(default: 0). The grouping pattern: read the total so far, with 0 for a category not seen yet, then set the new total. You will meet it again in the day-to-day program.

una run . prints:

Output
{"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: 1

units_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:

steps/18-map-forms/src/ledger.unauna
  let aisles = empty_map().with(key: 12, value: "garden").with(key: 3, value: "lighting")
  @console.print("{aisles}")
Output
{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:

steps/18-map-forms/src/ledger.unauna
  let same = restocked.without(key: "DESK-02")
  @console.print("{retired == same} {retired == stock}")
Output
true false

10.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:

src/stock.unadiff
--- 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)
Diagnostic
[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 explanation

The 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:

steps/18-map-forms/src/ledger.unauna
  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
Output
{"LAMP-01": 2, "RUG-07": 5} 2

The 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