---
title: "8.4 Kinds that contain themselves"
url: https://una-lang.org/en/learn/choices/kinds-that-contain-themselves/
release: v0.4.0
edition: "0.2"
---

# 8.4 Kinds that contain themselves

## 8.4.1 What a recursive kind is

Some data holds smaller data of the same shape. A store sells gift kits: a kit holds two products, and each of them may be a single item or another kit. A box of boxes, like a set of nesting dolls. A **recursive kind** is a kind that contains itself in one of its fields, so a value can hold another value of its own kind, which can hold another, as deep as the data goes.

## 8.4.2 Why a kind contains itself

With records of fixed fields, every level of nesting needs a kind of its own: a kit of items, a kit of kits of items, and so on, with a limit you choose in advance. A real catalog does not stop at the depth you planned. A recursive kind describes every depth with one declaration, and a recursive function, one that calls itself as in [section 6.1](https://una-lang.org/en/learn/functions/calls-in-depth-labels-the-order-of-evaluation-method-calls-on-your-own-kinds/#s6-1), walks every depth with one body.

## 8.4.3 How to write a recursive kind

```una include="steps/16-bundles/src/bundles.una#Bundle" title="src/bundles.una"
--- A product the store sells: one item, or a kit of two products, each of which may be a kit.
kind Bundle = Item(sku: Text, cents: Int) | Kit(first: Bundle, second: Bundle)
```

A kind can contain itself in two ways.

### 8.4.3.1 A variant that holds its own kind

`Bundle` is a sum whose variant `Kit` has two fields of kind `Bundle`, the kind being declared. The variant `Item` has none, and that matters: it is where a bundle stops. Every value of `Bundle` is built from items at the bottom, with kits above them.

### 8.4.3.2 Through an `Option`

A field may also hold an `Option` of the kind being declared ([section 7.1](https://una-lang.org/en/learn/failure/a-value-that-may-be-missing-option/#s7-1)): `Some` of a value, or `None`. Then `None` is where the value stops, and the kind needs no variant of its own for it. A category of products may sit inside a larger one:

```una include="steps/17-categories/src/kits.una" title="src/kits.una" verified="check, run"
module kits

--- A product category, inside a larger one or at the top. The kind contains itself through
--- an `Option`, and `None` is where the chain stops.
kind Category
  name: Text
  parent: Option[Category]

--- The full name of a category: its parents' names first, then its own.
path(category: Category) -> Text
=
  when category.parent
    is Some(parent) -> "{path(parent)} > {category.name}"
    is None -> category.name

--- How many levels a category sits below the top.
depth(category: Category) -> Int
=
  when category.parent
    is Some(parent) -> 1 + depth(parent)
    is None -> 0

pub main() -> Unit
  uses @console: Console[print]
=
  let lighting = Category(name: "Lighting", parent: None)
  let lamps = Category(name: "Lamps", parent: Some(lighting))
  let desk_lamps = Category(name: "Desk lamps", parent: Some(lamps))
  @console.print("{lamps}")
  @console.print("{path(desk_lamps)}, {depth(desk_lamps)} levels down")
```

```text include="steps/17-categories/expected/output.txt"
Category(name: "Lamps", parent: Some(Category(name: "Lighting", parent: None)))
Lighting > Lamps > Desk lamps, 2 levels down
```

`lamps` sits inside `lighting`, and `parent: None` marks the top. The first line prints `lamps` as you would build it, with its parent inside it. `path` and `depth` each take the category's `parent` apart with a `when`: for `Some(parent)`, they call themselves on the parent; for `None`, they stop.

Use an `Option` when a value holds at most one more of its kind, as a category has at most one parent. A field may also hold a list of values of its kind, for any number of parts; [chapter 10](https://una-lang.org/en/learn/collections/lists/#s10-1) teaches lists.

## 8.4.4 A reading kit, priced

A function over a recursive kind usually has one arm for each variant: the variant that stops gives its answer at once, and the variant that contains the kind calls the function again on each part and combines the answers.

:::steps
```una include="steps/16-bundles/src/bundles.una" title="src/bundles.una" verified="check, run"
module bundles

--- A product the store sells: one item, or a kit of two products, each of which may be a kit.
kind Bundle = Item(sku: Text, cents: Int) | Kit(first: Bundle, second: Bundle)

--- The price of a bundle: an item's price, or the prices of a kit's two parts added up.
price(bundle: Bundle) -> Int
=
  when bundle
    is Item(cents) -> cents
    is Kit(first, second) -> price(first) + price(second)

--- How many items a bundle holds. Check yourself: what does `main` print for `office`?
items(bundle: Bundle) -> Int
=
  when bundle
    is Item -> 1
    is Kit(first, second) -> items(first) + items(second)

pub main() -> Unit
  uses @console: Console[print]
=
  let lamp = Item(sku: "LAMP-01", cents: 1990)
  let bulb = Item(sku: "BULB-02", cents: 350)
  let reading = Kit(first: lamp, second: Kit(first: bulb, second: bulb))
  @console.print("reading kit: {price(reading)} cents")
  @console.print("{reading}")
  let desk = Item(sku: "DESK-02", cents: 15900)
  let office = Kit(first: desk, second: reading)
  @console.print("office kit: {items(office)} items")
```

1. **`is Item(cents) -> cents`.** The bottom: an item's price is its own.
2. **`is Kit(first, second) -> price(first) + price(second)`.** A kit's price is the price of each part, added. Each call works on a smaller bundle, so the calls end at the items.
3. **`Kit(first: lamp, second: Kit(first: bulb, second: bulb))`.** A kit of a lamp and a kit of two bulbs: two levels.
:::

`una run .` prints, among other lines:

```text include="steps/16-bundles/expected/output.txt#L1-L2"
reading kit: 2690 cents
Kit(first: Item(sku: "LAMP-01", cents: 1990), second: Kit(first: Item(sku: "BULB-02", cents: 350), second: Item(sku: "BULB-02", cents: 350)))
```

The lamp costs 1990 and each bulb 350: 1990 + 350 + 350 = 2690. The second line prints the kit as you would build it, every level inside the one above.

## 8.4.5 How a recursive kind behaves

### 8.4.5.1 Every kind needs a value that ends

Every value of a kind is finite: it must be possible to build one without going on forever. A kind whose every variant needs another value of the same kind has no such value. Declare one:

```diff include="steps/16-bundles..steps/18-endless:src/bundles.una" title="src/bundles.una" context="0"
--- a/src/bundles.una
+++ b/src/bundles.una
@@ -4,0 +5,3 @@
+
+--- A crate that always holds another crate: no value of it can ever be built.
+kind Crate = | Holds(inner: Crate)
```

```text include="steps/18-endless/expected/rendered.txt"
[U2002] Error: kind `Crate` has no finite value: every variant contains a kind without one; add a variant without it, as `End`
   ╭─[ src/bundles.una:7:6 ]
   │
 7 │ kind Crate = | Holds(inner: Crate)
   │      ──┬──
   │        ╰──── kind `Crate` has no finite value: every variant contains a kind without one; add a variant without it, as `End`
   │
   │ Note: run `una explain U2002` for an explanation
───╯
```

A `Crate` would hold a crate, which would hold a crate, without end, so no `Crate` can ever be built. U2002 says so, and its message gives the repair: a variant that does not contain the kind, such as `End`. In `Bundle`, `Item` is that variant, and in `Category`, `None` plays that part.

### 8.4.5.2 A `when` over it needs no special form

A recursive kind is a sum or a record like any other, so a `when` over it follows every rule of [section 8.2](https://una-lang.org/en/learn/choices/when-in-full/#s8-2): an arm for each variant, or an `else`. The recursion is in the function, not in the `when`.

### 8.4.5.3 A recursive call has a limit

Each level of a bundle is one more call of `price` waiting for its parts. A run has a limit on how many calls may wait at once, and a value deep enough to exceed it stops the run with U6003, as [section 6.1](https://una-lang.org/en/learn/functions/calls-in-depth-labels-the-order-of-evaluation-method-calls-on-your-own-kinds/#s6-1) said; [section 16.4](https://una-lang.org/en/learn/memory/limits-call-depth-and-memory/#s16-4) covers the limits. Store data such as kits and categories nests a few levels, far below the limit.

## 8.4.6 A recursive kind, records or a list

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

| Your data… | Use |
| --- | --- |
| Has a fixed depth, such as a parcel and its address | Records, one per level |
| Holds parts that are each a whole of the same kind | A recursive kind, with a variant that ends |
| Holds at most one more of its kind, such as a parent | A field of `Option` of the kind |
| Is many values of one kind, in order | A list ([chapter 10](https://una-lang.org/en/learn/collections/lists/#s10-1)) |
:::

## 8.4.7 Check yourself: recursive kinds

`items` counts the items of a bundle:

```una include="steps/16-bundles/src/bundles.una#items" title="src/bundles.una"
--- How many items a bundle holds. Check yourself: what does `main` print for `office`?
items(bundle: Bundle) -> Int
=
  when bundle
    is Item -> 1
    is Kit(first, second) -> items(first) + items(second)
```

`office` is `Kit(first: desk, second: reading)`, where `desk` is an item and `reading` is the reading kit of this section. What does `items(office)` give?

:::answer Show the answer
```text include="steps/16-bundles/expected/output.txt#L3"
office kit: 4 items
```

`items(office)` is `items(desk) + items(reading)`. The desk is an item, 1. The reading kit is `items(lamp)` plus the items of its inner kit of two bulbs, 1 + 2 = 3. In all, 1 + 3 = 4. The bulb is counted twice, since the kit holds two of it.
:::
