Home / Learn / 8 Choosing
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
--- 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:
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")Category(name: "Lamps", parent: Some(Category(name: "Lighting", parent: None)))
Lighting > Lamps > Desk lamps, 2 levels downlamps 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.
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")is Item(cents) -> cents. The bottom: an item's price is its own.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.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:
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:
--- 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)[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:
--- 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
office kit: 4 itemsitems(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.