Home / Learn / 8 Choosing

Release v0.4.0Edition 0.2

8.4 Kinds that contain themselves

Page 5 of 10

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, walks every depth with one body.

8.4.3 How to write a recursive kind

src/bundles.unauna
--- 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): 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:

src/kits.unacheckrununa
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")
Output
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 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.

src/bundles.unacheckrununa
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:

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

src/bundles.unadiff
--- 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)
Diagnostic
[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: 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 said; section 16.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

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)

8.4.7 Check yourself: recursive kinds

items counts the items of a bundle:

src/bundles.unauna
--- 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?

Show the answer
Output
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.

Next:8.5 Day-to-day: shipment tracking