---
title: "10.3 Functions over lists: map, filter and fold"
url: https://una-lang.org/en/learn/collections/functions-over-lists-map-filter-and-fold/
release: v0.4.0
edition: "0.2"
---

# 10.3 Functions over lists: map, filter and fold

## 10.3.1 What a function over a list is

A loop says *how* to walk a list: start a name, visit each element, update the name. Most walks have one of a few shapes, and the prelude has a function for each shape. You give it the list and the one step that differs, and it does the walking.

Think of instructions to a stock clerk. "Put a new price tag on every item" changes each item. "Pull every item past its date" keeps some items. "Count the units on the shelf" turns many items into one number. "Find me the first blue mug" stops at a match. Each instruction names one shape of work and one rule. In Una, these are `map`, `filter`, `fold` and `first_where`, and the rule is a function you pass to them, often a lambda.

A function that takes another function as an argument is a **higher-order function**. `priced` of [section 10.2](https://una-lang.org/en/learn/collections/functions-as-values-and-lambdas/#s10-2) is one, and so are the four of this section.

## 10.3.2 Why the prelude walks the list for you

Here are three loops over a cart: one prices each line, one leaves out the gift cards, and one counts the units.

```una include="steps/13-loops-repeat/src/cart.una#line_totals..units" title="steps/13-loops-repeat/src/cart.una"
--- What each line costs, in cents.
line_totals(lines: List[CartLine]) -> List[Int]
=
  let edit totals: List[Int] = []
  for line in lines
    totals = totals.append(item: line.quantity * line.cents)
  totals

--- The lines that are not gift cards.
goods(lines: List[CartLine]) -> List[CartLine]
=
  let edit kept: List[CartLine] = []
  for line in lines
    if not line.sku.starts_with(prefix: "GIFT-")
      kept = kept.append(item: line)
  kept

--- How many units the cart holds.
units(lines: List[CartLine]) -> Int
=
  let edit count = 0
  for line in lines
    count = count + line.quantity
  count
```

```text include="steps/13-loops-repeat/expected/output.txt"
[3980, 5000] 1 3
```

They work, and they are almost the same code. Each declares a name that starts empty or at 0, walks the list, updates the name, and gives it back. Only one line in each says what the function is for. A reader has to read all of them to find that line, and each copy of the walk is one more place to get the start value or the update wrong. With the prelude's functions, the walk is written once, in the prelude, and your code keeps only the line that matters.

## 10.3.3 How to write `map`, `filter`, `fold` and `first_where`

Each one is called with method syntax on a list, and takes its function under a label that says what the function does: `each`, `keep` or `step`. The step for this part works on prices and SKUs:

```una include="steps/14-list-functions/src/prices.una#L1-L11" title="steps/14-list-functions/src/prices.una"
module prices

--- A price with 10% sales tax added, rounded down.
with_tax(cents: Int) -> Int = cents + cents / 10

pub main() -> Unit
  uses @console: Console[print]
=
  let prices = [1990, 4500, 850]
  let skus = ["LAMP-01", "RUG-07", "MUG-11"]
  let empty: List[Int] = []
```

### 10.3.3.1 A new value for each element: `map(each:)`

`map` calls its function on each element and gives the list of the results, in the same order and of the same length. The function may be a declared function, passed by its name, or a lambda. Its result may have another type than the elements: the second call gives SKUs in lower case, and the third gives a `Bool` for each price.

```una include="steps/14-list-functions/src/prices.una#L12-L14" title="steps/14-list-functions/src/prices.una"
  @console.print("map: {prices.map(each: with_tax)}")
  @console.print("map: {skus.map(each: fn(sku) -> sku.to_lower())}")
  @console.print("map: {prices.map(each: fn(cents) -> cents >= 2000)}")
```

```text include="steps/14-list-functions/expected/output.txt#L1-L3"
map: [2189, 4950, 935]
map: ["lamp-01", "rug-07", "mug-11"]
map: [false, true, false]
```

`with_tax` is passed by name, without parentheses: you hand over the function, and `map` calls it. 1990 plus a tenth, rounded down, is 2189.

### 10.3.3.2 Some of the elements: `filter(keep:)`

`filter` keeps the elements for which its function gives `true`, in their order. The function must give a `Bool`.

```una include="steps/14-list-functions/src/prices.una#L15-L18" title="steps/14-list-functions/src/prices.una"
  let limit = 2000
  let above = prices.filter(keep: fn(cents) -> cents >= limit)
  let mugs = skus.filter(keep: fn(sku) -> sku.starts_with(prefix: "MUG"))
  @console.print("filter: {above} {mugs}")
```

```text include="steps/14-list-functions/expected/output.txt#L4"
filter: [4500] ["MUG-11"]
```

The first lambda reads `limit`, a name declared outside it, as it was when the lambda was made.

### 10.3.3.3 One value from all the elements: `fold(initial:, step:)`

`fold` carries one value from the first element to the last. It starts from `initial`. At each element it calls `step` with two arguments, the value so far and the element, and the step's result becomes the new value so far. The last value is the result.

```una include="steps/14-list-functions/src/prices.una#L19-L21" title="steps/14-list-functions/src/prices.una"
  let total = prices.fold(initial: 0, step: fn(sum, cents) -> sum + cents)
  let top = prices.fold(initial: 0, step: fn(best, cents) -> max(best, b: cents))
  @console.print("fold: {total} and {top}")
```

```text include="steps/14-list-functions/expected/output.txt#L5"
fold: 7340 and 4500
```

The first `fold` adds up: 0 + 1990 = 1990, + 4500 = 6490, + 850 = 7340. The second keeps the largest price seen so far with `max`, whose second parameter is named `b`. The value so far may have any type, the same for `initial`, the step's first parameter, and its result.

### 10.3.3.4 The first match: `first_where(keep:)`

`first_where` gives the first element for which its function gives `true`, as an `Option`, and stops there. When no element matches, it gives `None`.

```una include="steps/14-list-functions/src/prices.una#L22-L24" title="steps/14-list-functions/src/prices.una"
  let rug = skus.first_where(keep: fn(sku) -> sku.starts_with(prefix: "RUG"))
  let desk = skus.first_where(keep: fn(sku) -> sku.starts_with(prefix: "DESK"))
  @console.print("first_where: {rug} and {desk}")
```

```text include="steps/14-list-functions/expected/output.txt#L6"
first_where: Some("RUG-07") and None
```

### 10.3.3.5 One after another: chaining

The result of one call is a list, so the next call can follow it with another dot. Read a chain from left to right: keep the prices under 2000, add tax to each, and add them up.

```una include="steps/14-list-functions/src/prices.una#L25-L26" title="steps/14-list-functions/src/prices.una"
  let cheap = prices.filter(keep: fn(cents) -> cents < 2000).map(each: with_tax).sum()
  @console.print("chained: {cheap}")
```

```text include="steps/14-list-functions/expected/output.txt#L7"
chained: 3124
```

1990 and 850 are under 2000; with tax they are 2189 and 935, and their sum is 3124.

## 10.3.4 Pricing a cart without a loop

The tools together, in a store example. The step prices a cart, counts its units, and decides whether it ships free:

:::steps
```una include="steps/15-higher-order/src/pricing.una" title="steps/15-higher-order/src/pricing.una" verified="check, run"
module pricing

--- One line of a cart: a SKU, how many units, and the price of one unit in cents.
kind CartLine
  sku: Text
  quantity: Int
  cents: Int

--- What one line costs, in cents.
line_cents(line: CartLine) -> Int = line.quantity * line.cents

pub main() -> Unit
  uses @console: Console[print]
=
  let lamp = CartLine(sku: "LAMP-01", quantity: 2, cents: 1990)
  let rug = CartLine(sku: "RUG-07", quantity: 1, cents: 4500)
  let gift = CartLine(sku: "GIFT-50", quantity: 1, cents: 5000)
  let cart = [lamp, rug, gift]
  @console.print("{cart.map(each: line_cents)}")
  let big = cart.filter(keep: fn(line) -> line.quantity >= 2)
  @console.print("{big.map(each: fn(line) -> line.sku)}")
  let units = cart.fold(initial: 0, step: fn(sum, line) -> sum + line.quantity)
  @console.print("{units} units")
  @console.print("free shipping: {ships_free(cart)}")

--- Whether a cart ships for free: 10000 cents or more, not counting gift cards.
ships_free(lines: List[CartLine]) -> Bool
=
  let goods = lines.filter(keep: fn(line) -> not line.sku.starts_with(prefix: "GIFT-"))
  goods.map(each: line_cents).sum() >= 10000
```

1. **`cart.map(each: line_cents)`.** A function declared with a name is passed by that name.
2. **`fn(line) -> line.quantity >= 2`.** A lambda. Its parameter's type, `CartLine`, comes from the list it is used on.
3. **`fold(initial: 0, step: fn(sum, line) -> sum + line.quantity)`.** The step takes the value so far and the next element. Here it counts units; `initial` is the result for an empty cart.
4. **`ships_free`.** The same tools in a function: leave out the gift cards, price each line, add up, compare. Each step is one call, and the result of one is the input of the next.
:::

`una run .` prints:

```text include="steps/15-higher-order/expected/output.txt"
[3980, 4500, 5000]
["LAMP-01"]
4 units
free shipping: false
```

The three loops of [Why the prelude walks the list for you](#why-the-prelude-walks-the-list-for-you) are each one call here: `map(each: line_cents)`, a `filter`, and a `fold`.

## 10.3.5 How the functions behave

### 10.3.5.1 Order, and how often the function is called

`map`, `filter`, `fold` and `first_where` call their function on the elements from first to last, once per element. `first_where` stops after the first element it accepts, so the elements after it are never tested.

### 10.3.5.2 Functions over an empty list

Each one has a plain answer for an empty list. `map` gives `[]`, `fold` gives its `initial` value, `first_where` gives `None`, and `sum` gives 0:

```una include="steps/14-list-functions/src/prices.una#L27-L30" title="steps/14-list-functions/src/prices.una"
  let doubled = empty.map(each: fn(cents) -> cents * 2)
  let counted = empty.fold(initial: 0, step: fn(sum, cents) -> sum + cents)
  let first_big = empty.first_where(keep: fn(cents) -> cents > 0)
  @console.print("empty: {doubled} {counted} {first_big}")
```

```text include="steps/14-list-functions/expected/output.txt#L8"
empty: [] 0 None
```

So choose `initial` as the right answer for "nothing": 0 for a total, and for a largest value, one that no element can be below, such as 0 for prices.

### 10.3.5.3 The function must fit

The function you pass must take the element's type and give what the call needs. `filter` needs a `Bool` from `keep`. Give it a number instead:

```diff include="steps/14-list-functions..steps/16-filter-result:src/prices.una" context="1" title="src/prices.una"
--- a/src/prices.una
+++ b/src/prices.una
@@ -15,3 +15,3 @@
   let limit = 2000
-  let above = prices.filter(keep: fn(cents) -> cents >= limit)
+  let above = prices.filter(keep: fn(cents) -> cents - limit)
   let mugs = skus.filter(keep: fn(sku) -> sku.starts_with(prefix: "MUG"))
```

`una check .` reports:

```text include="steps/16-filter-result/expected/rendered.txt"
[U2001] Error: expected `Bool`, found `Int`
    ╭─[ src/prices.una:16:48 ]
    │
 16 │   let above = prices.filter(keep: fn(cents) -> cents - limit)
    │                                                ──────┬──────
    │                                                      ╰──────── expected `Bool`, found `Int`
    │
    │ Note: run `una explain U2001` for an explanation
────╯
```

The message says what `keep` must give, a `Bool`, and what the lambda gives, an `Int`. The mark points at the lambda's body, `cents - limit`, which is a number, not a yes-or-no answer. The fix is a comparison: `cents >= limit`.

### 10.3.5.4 A function that can fail

`map`, `filter`, `fold` and `first_where` declare `fails of` their function, as `total_with` of [section 10.2](https://una-lang.org/en/learn/collections/functions-as-values-and-lambdas/#s10-2) does. So you may pass them a function that can fail, such as `listed`, and the call then takes a clause:

```una include="steps/10-fails-of/src/prices.una#L54-L58" title="steps/10-fails-of/src/prices.una"
  let found = ["LAMP-01", "DESK-02"].map(each: listed)
    if error use []
  let unknown = ["LAMP-01", "VASE-03"].map(each: listed)
    if error use []
  @console.print("map: {found} {unknown}")
```

```text include="steps/10-fails-of/expected/output.txt#L3"
map: [1990, 15900] []
```

The first list has a price for each SKU. In the second, `listed` fails at `VASE-03`, and `map` stops at that first failure: the whole call fails, and the clause gives `[]`. A function that cannot fail needs no clause, as in every other call of this section.

### 10.3.5.5 What a lambda can see

A lambda sees the values of the names around it as they were when it was made, and it cannot assign a `let edit` name outside it: its body is one expression, not a list of steps. To build up a value, use `fold`, or a `for` loop.

## 10.3.6 A function over the list, or a loop

:::decide
**Which to use:**

| You want to… | Use |
| --- | --- |
| A new list with one result per element | `map` |
| Some of the elements | `filter` |
| One element, the first that matches | `first_where` |
| A total of integers | `map`, then `sum()` |
| One value built from all the elements | `fold`, or `for` with `let edit` |
| Several results at once, or a step with an `if` and a few lines | `for` with `let edit` |
| A step for each element that prints | `for` |
:::

The rows with two answers have two right answers. Choose the one a reader follows faster: a `fold` with a one-line step, or a loop when the step needs room.

## 10.3.7 Check yourself: functions over lists

Predict what this prints before you open the answer:

```una include="steps/14-list-functions/src/prices.una#L31-L33" title="steps/14-list-functions/src/prices.una"
  let picked = [5, 12, 8].filter(keep: fn(units) -> units > 6).map(each: fn(units) -> units * 2)
  let longest = skus.fold(initial: 0, step: fn(best, sku) -> max(best, b: sku.len))
  @console.print("question: {picked} {longest}")
```

:::answer Show the answer
```text include="steps/14-list-functions/expected/output.txt#L9"
question: [24, 16] 7
```

`filter` keeps 12 and 8, the units above 6, in their order, and `map` doubles each: `[24, 16]`. The `fold` keeps the longest length seen so far: `LAMP-01` has 7 characters, `RUG-07` 6 and `MUG-11` 6, so the result is 7.
:::
