Home / Learn / 10 Collections
10.1 Lists
Page 2 of 11
10.1.1 What a list is
A list is one value that holds several values of the same type, one after another. Think of the lines of a receipt: there may be one line or forty, they come in a fixed order, and each line is the same sort of thing. A list works the same way. The values it holds are its elements, and each element has a position, its place in the order.
A few words name the parts, and the rest of this chapter uses them:
- A list literal writes a list's elements between brackets, separated by commas:
[2, 1, 3]. A literal is a value written out in the code, as3or"LAMP-01"is (section 2.1). - The type of a list names the type of its elements:
List[Int]is a list of whole numbers, andList[Text]a list of texts.Listis a generic kind, as in section 4.4: it takes another type between brackets, asOption[Int]does. - A position, also called an index, counts from 0. In
[2, 1, 3], the element at position 0 is 2, and the element at position 2 is 3. - The length of a list is how many elements it holds.
[2, 1, 3]has a length of 3, and[], the empty list, a length of 0.
The prelude, the set of functions every module has without importing anything (section 3.2), gives lists most of what a program needs: adding an element, adding up, sorting, searching. You call these functions with method syntax: [2, 1, 3].sum() is the call sum([2, 1, 3]).
10.1.2 Why a program needs lists
Without a list, every value needs a name of its own. Here is a function that counts the units of a cart, with one parameter for each line of the cart:
module cart
--- The units in a cart of exactly three lines: one parameter for each line.
units_of_three(first: Int, second: Int, third: Int) -> Int = first + second + third
--- Prints the units of a cart of three lines.
pub main() -> Unit
uses @console: Console[print]
=
@console.print("{units_of_three(2, second: 1, third: 3)} units")6 unitsIt works for a cart of exactly three lines. A cart of four lines needs another function, with four parameters, and a cart of one line a third. A real cart may hold any number of lines, and the program learns that number only when it runs. A list solves that: List[Int] is one type for any number of quantities, so one name and one parameter hold the whole cart, and the functions of this chapter work on it whatever its length.
Each example of this chapter is a package, made as chapter 2 explains, and the chapter's download, 10-collections.tar.gz, holds them all. Every package of this chapter uses edition 0.2, the edition that brings maps, sort, set, JSON and the functions that take failing functions; a package of edition 0.1 has none of them.
10.1.3 How to write a list: a cart and its receipt
Start with the quantities of a cart, then the SKUs on its receipt. A SKU, a stock-keeping unit, is the code a store gives each product, such as LAMP-01.
module cart
pub main() -> Unit
uses @console: Console[print]
=
let quantities = [2, 1, 3]
let more = quantities.append(item: 4)
@console.print("{quantities} then {more}")
@console.print("{more.len} lines, {more.sum()} units")
@console.print("a line of 3 units: {more.contains(item: 3)}")
let skus = ["RUG-07", "LAMP-01", "DESK-02"]
@console.print(receipt(skus))
--- The SKUs of a cart in the order a receipt lists them.
receipt(skus: List[Text]) -> Text = skus.sort().join(separator: ", ")[2, 1, 3]. A list literal. Every element has the same type, hereInt, so the list is aList[Int]. You do not write the type: Una takes it from the elements.quantities.append(item: 4). This gives back a new list with4at the end.quantitiesitself does not change: the first line of the output shows both lists.more.len. The number of elements, as onText..lenis built in and is written without parentheses:more.len()does not check.more.sum()andmore.contains(item: 3). The sum of a list of integers, and whether some element equals 3.skus.sort().join(separator: ", ").sortgives back the elements in ascending order, andjoinputs a list of texts together, with the separator between each two. The result ofsortis a list, so.joincan follow it on the same line.receipt(skus: List[Text]). A parameter of a list type, written like any other parameter.
una run . prints:
[2, 1, 3] then [2, 1, 3, 4]
4 lines, 10 units
a line of 3 units: true
DESK-02, LAMP-01, RUG-07A list in an interpolation is written as you would type it in Una, with brackets, and with quotes around texts.
10.1.4 Visiting each element: for over a list
Section 9.1 walked ranges of numbers and the characters of a text with for. A for loop walks a list the same way: for line in cart runs its body once for each element, from the first to the last, and inside the body line names the element of that turn. Think of a cashier who scans the items of a basket one at a time: the same step, done once per item, in order.
The step of this part prints a shelf list and a receipt:
--- 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
--- The total of a cart in cents: one turn of the loop for each line.
total(lines: List[CartLine]) -> Int
=
let edit sum = 0
for line in lines
sum = sum + line.quantity * line.cents
sum--- Prints a shelf list, then a receipt with one line for each line of the cart.
pub main() -> Unit
uses @console: Console[print]
=
let skus = ["LAMP-01", "RUG-07", "DESK-02"]
for sku in skus
@console.print("on the shelf list: {sku}")
let lamp = CartLine(sku: "LAMP-01", quantity: 2, cents: 1990)
let rug = CartLine(sku: "RUG-07", quantity: 1, cents: 4500)
let cart = [lamp, rug]
for line in cart
if line.quantity >= 2
@console.print("{line.sku}: {line.quantity} units, bulk")
else
@console.print("{line.sku}: {line.quantity} unit")
@console.print("total: {total(cart)} cents")
let empty: List[CartLine] = []
for line in empty
@console.print("never printed: {line.sku}")
@console.print("an empty cart: {total(empty)} cents")
for sku in skus
for size in ["S", "L"]
@console.print("label {sku}-{size}")una run . prints:
on the shelf list: LAMP-01
on the shelf list: RUG-07
on the shelf list: DESK-02
LAMP-01: 2 units, bulk
RUG-07: 1 unit
total: 8480 cents
an empty cart: 0 cents
label LAMP-01-S
label LAMP-01-L
label RUG-07-S
label RUG-07-L
label DESK-02-S
label DESK-02-L10.1.4.1 One element at a time
for sku in skus runs @console.print three times, once for each SKU, in the order of the list. sku is a new name in each turn, and it exists only inside the loop's body. It is a plain name: the body cannot assign it, since it is not let edit.
10.1.4.2 A running total over a list
total is the pattern of section 9.2 over a list: a let edit name declared before the loop, sum, updated at each turn, and given back after the loop. Here each turn adds what one line costs, its quantity times its price: 2 × 1990 + 1 × 4500 = 8480.
10.1.4.3 A choice at each turn
The body may hold any steps, here an if with two branches (section 8.1): a line of two units or more is printed as bulk.
10.1.4.4 An empty list
A loop over an empty list runs its body zero times, so never printed never appears, and total gives back the value sum started with, 0. The empty list needs its type written, List[CartLine], since it has no element to take one from.
10.1.4.5 A loop inside a loop
The last loop prints a label for each SKU in each size. The inner loop runs completely, for both sizes, at each turn of the outer one, so 3 SKUs and 2 sizes give 6 labels. A list literal such as ["S", "L"] may stand right after in.
10.1.5 What the prelude does with a list
The next step shows the other forms of a list, and the prelude's functions for lists. Its main prints one line per form:
--- The size of a T-shirt. Its variants carry no data, so they have an order: the order of
--- their declaration.
kind Size = Small | Medium | Large
--- The counts on a shelf, after a recount of the shelf at `position`.
recount(counts: List[Int], position: Int, counted: Int) -> List[Int]
requires 0 <= position and position < counts.len
=
let edit fixed = counts
edit fixed.set(index: position, item: counted)
fixed10.1.5.1 Literals: empty, of values, of variants, of lists
let empty: List[Text] = []
let counts = [4, 0, 7]
let sizes = [Large, Small, Medium]
let aisles = [[1, 2], [3]]
@console.print("{empty.len} {counts.len} {sizes.len} {aisles.len}")0 3 3 2[]is the empty list. It has no element to take a type from, so you write the type on the name:let empty: List[Text] = [].[4, 0, 7]is aList[Int], and its type comes from its elements.[Large, Small, Medium]holds variants of the sum kindSize, so it is aList[Size].[[1, 2], [3]]is a list whose elements are lists: aList[List[Int]], here two aisles with their shelf numbers.
Canonical form keeps a list literal on one line, however long it is.
10.1.5.2 Length and emptiness: len and is_empty
@console.print("{empty.is_empty()} {counts.is_empty()}")true falseis_empty() is true exactly when len is 0.
10.1.5.3 Reading one element: first and at
@console.print("{counts.first()} {counts.at(index: 2)} {counts.at(index: 3)} {empty.first()}")Some(4) Some(7) None Nonecounts.first() reads position 0, and counts.at(index: 2) reads position 2. Una has no counts[2] syntax. Both give an Option: Some with the element, or None when there is no element there, as for position 3 of a list of three, or the first element of an empty list. Use what they give with when or or_else, as section 7.1 shows.
10.1.5.4 Searching and adding up: contains, sum and join
let receipt = empty.join(separator: ", ")
@console.print("{counts.contains(item: 0)} {counts.sum()} '{receipt}'")true 11 ''contains(item: 0) is true when some element equals 0. sum() adds up a list of numbers, and gives 0 for an empty list; like every Int, the sum has no upper limit. join on an empty list gives the empty text, which the quotes around it make visible.
10.1.5.5 Sorting: sort
@console.print("{counts.sort()} {sizes.sort()}")[0, 4, 7] [Small, Medium, Large]sort gives back a new list in ascending order. It works on any type with an order, the constraint Ord of section 4.4: Int, Text, the fixed-width integers, and sum kinds whose variants carry no data, in the order the variants are declared, which is why Small comes before Large. It is stable: elements that are equal keep the order they had. A record such as a cart line has no order of its own, and Sorting records shows what the checker says when you try.
10.1.5.6 Replacing one element: set
append gives back a new list with one more element. To replace the element at a position, set changes a list in place:
@console.print("{recount(counts, position: 1, counted: 5)} {counts}")[4, 5, 7] [4, 0, 7]recount copies its parameter into let edit fixed, a name it may change, then writes edit fixed.set(index: position, item: counted). The word edit before the call marks the line where fixed changes: set takes its list as an edit parameter, which section 16.2 explains. set has a precondition, a position that exists: 0 <= index and index < xs.len. So recount states the same condition in its requires line (section 5.1), and each caller of recount must meet it. The caller's counts keeps its values: the copy changed, not the original.
10.1.5.7 Comparing lists: ==
@console.print("{counts == [4, 0, 7]} {counts == [0, 4, 7]}")true falseTwo lists are equal when they hold equal elements in the same order. The same elements in another order make a different list.
10.1.6 How a list behaves
10.1.6.1 Every element has the list's type
A list holds values of one type. Write a count as a word in the middle of a list of numbers:
--- a/src/shelf.una
+++ b/src/shelf.una
@@ -18,3 +18,3 @@
let empty: List[Text] = []
- let counts = [4, 0, 7]
+ let counts = [4, "zero", 7]
let sizes = [Large, Small, Medium]una check . reports:
[U2001] Error: expected `Int`, found `Text`
╭─[ src/shelf.una:19:20 ]
│
19 │ let counts = [4, "zero", 7]
│ ───┬──
│ ╰──── expected `Int`, found `Text`
│
│ Note: run `una explain U2001` for an explanation
────╯The first line names the problem: an element was expected to be an Int, and a Text was found. The mark points at "zero", the element that does not fit; the list took its type, Int, from its first element. To keep values of several shapes in one list, declare a sum kind with one variant for each shape (section 4.2), and make the list a list of that kind.
10.1.6.2 A list is a value
A list never changes behind your back. append and sort give back new lists, and the list you called them on keeps its elements. A function that receives a list cannot change the caller's list: recount changed its own copy. A name changes only where the code says so: with let edit and an assignment, or with edit before a call.
10.1.6.3 Positions and absence
Positions count from 0, so the last element of a list of length n is at position n - 1. Reading a position never stops the program: at gives None for a position that is negative or past the end. That is why it gives an Option.
10.1.6.4 Adding at the end without copying
Note
A list is a value: append gives back a new list, and the old one is unchanged for anyone who still holds it. When nothing else holds the list, una may reuse it and update it in place instead of copying it; whether it does is not something a program can observe, and the language does not promise it.
10.1.7 A list, a loop or a function of the prelude
Which to use:
| You want to… | Use |
|---|---|
| Values in an order, the same value maybe twice | a list |
| A step for each element, such as printing it | for x in xs |
| A total, a test or a sorted copy | sum, contains, sort and the other prelude functions |
| One element, by its position | at(index:) or first(), which give an Option |
| A value found by a key, such as the stock of a SKU | a map, section 10.4 |
10.1.8 Check yourself: lists
Read the two lines, and predict what they print before you open the answer:
let shelf = [3, 1, 2]
@console.print("{shelf.append(item: 1).sort()} {shelf.len}")Show the answer
[1, 1, 2, 3] 3append gives back a new list, [3, 1, 2, 1], and sort puts it in order; the two equal 1s both stay. shelf itself still has 3 elements, since append never changes the list it is called on.