---
title: "10.4 Maps"
url: https://una-lang.org/en/learn/collections/maps/
release: v0.4.0
edition: "0.2"
---

# 10.4 Maps

## 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.

```una include="steps/17-groups-by-hand/src/sales.una" title="steps/17-groups-by-hand/src/sales.una" verified="check, run"
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:

```text include="steps/17-groups-by-hand/expected/output.txt"
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:

```una include="steps/18-map-forms/src/ledger.una#stock_after_day" title="steps/18-map-forms/src/ledger.una"
--- 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()`.

```una include="steps/18-map-forms/src/ledger.una#L17-L19" title="steps/18-map-forms/src/ledger.una"
  let empty: Map[Text, Int] = empty_map()
  let stock = stock_after_day()
  @console.print("{empty} {empty.len} / {stock} {stock.len}")
```

```text include="steps/18-map-forms/expected/output.txt#L1"
{} 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:

- the name is declared `let edit`, since only an editable name may change ([section 9.2](https://una-lang.org/en/learn/loops/names-that-change-let-edit/#s9-2));
- the call starts with the word `edit`, which marks the line where the map changes, as for a list's `set` ([section 16.2](https://una-lang.org/en/learn/memory/passing-a-value-in-and-out-edit/#s16-2) explains `edit` at 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`:

```una include="steps/18-map-forms/src/ledger.una#L20-L22" title="steps/18-map-forms/src/ledger.una"
  let restocked = stock.with(key: "RUG-07", value: 9)
  let retired = restocked.without(key: "DESK-02")
  @console.print("{restocked} {retired} {stock}")
```

```text include="steps/18-map-forms/expected/output.txt#L2"
{"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.

```una include="steps/18-map-forms/src/ledger.una#L23-L27" title="steps/18-map-forms/src/ledger.una"
  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}")
```

```text include="steps/18-map-forms/expected/output.txt#L3"
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:

```una include="steps/18-map-forms/src/ledger.una#L28-L30" title="steps/18-map-forms/src/ledger.una"
  @console.print("{restocked.keys()} {restocked.values()}")
  for entry in restocked.entries()
    @console.print("{entry.key} has {entry.value}")
```

```text include="steps/18-map-forms/expected/output.txt#L4-L7"
["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
```una include="steps/19-maps/src/stock.una" title="steps/19-maps/src/stock.una" verified="check, run"
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:

```text include="steps/19-maps/expected/output.txt"
{"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:

```una include="steps/18-map-forms/src/ledger.una#L31-L32" title="steps/18-map-forms/src/ledger.una"
  let aisles = empty_map().with(key: 12, value: "garden").with(key: 3, value: "lighting")
  @console.print("{aisles}")
```

```text include="steps/18-map-forms/expected/output.txt#L8"
{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](https://una-lang.org/en/learn/collections/exercises/#exercise-3-categories-by-revenue).

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

```una include="steps/18-map-forms/src/ledger.una#L33-L34" title="steps/18-map-forms/src/ledger.una"
  let same = restocked.without(key: "DESK-02")
  @console.print("{retired == same} {retired == stock}")
```

```text include="steps/18-map-forms/expected/output.txt#L9"
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:

```diff include="steps/19-maps..steps/20-record-key:src/stock.una" context="1" title="src/stock.una"
--- 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)
```

```text include="steps/20-record-key/expected/rendered.txt#L1-L8"
[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](https://una-lang.org/en/learn/kinds/generic-kinds-and-constraints/#s4-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

:::decide
**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:

```una include="steps/18-map-forms/src/ledger.una#L35-L36" title="steps/18-map-forms/src/ledger.una"
  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}")
```

:::answer Show the answer
```text include="steps/18-map-forms/expected/output.txt#L10"
{"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.
:::
