Home / Learn / 10 Collections

Release v0.4.0Edition 0.2

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:

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:

steps/01-fixed-cart/src/cart.unacheckrununa
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")
Output
6 units

It 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.

steps/02-lists/src/cart.unacheckrununa
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: ", ")
  1. [2, 1, 3]. A list literal. Every element has the same type, here Int, so the list is a List[Int]. You do not write the type: Una takes it from the elements.
  2. quantities.append(item: 4). This gives back a new list with 4 at the end. quantities itself does not change: the first line of the output shows both lists.
  3. more.len. The number of elements, as on Text. .len is built in and is written without parentheses: more.len() does not check.
  4. more.sum() and more.contains(item: 3). The sum of a list of integers, and whether some element equals 3.
  5. skus.sort().join(separator: ", "). sort gives back the elements in ascending order, and join puts a list of texts together, with the separator between each two. The result of sort is a list, so .join can follow it on the same line.
  6. receipt(skus: List[Text]). A parameter of a list type, written like any other parameter.

una run . prints:

Output
[2, 1, 3] then [2, 1, 3, 4]
4 lines, 10 units
a line of 3 units: true
DESK-02, LAMP-01, RUG-07

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

steps/03-for-lists/src/receipt.unacheckuna
--- 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
steps/03-for-lists/src/receipt.unacheckrununa
--- 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:

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

10.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:

steps/04-list-forms/src/shelf.unauna
--- 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)
  fixed

10.1.5.1 Literals: empty, of values, of variants, of lists

steps/04-list-forms/src/shelf.unauna
  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}")
Output
0 3 3 2

Canonical form keeps a list literal on one line, however long it is.

10.1.5.2 Length and emptiness: len and is_empty

steps/04-list-forms/src/shelf.unauna
  @console.print("{empty.is_empty()} {counts.is_empty()}")
Output
true false

is_empty() is true exactly when len is 0.

10.1.5.3 Reading one element: first and at

steps/04-list-forms/src/shelf.unauna
  @console.print("{counts.first()} {counts.at(index: 2)} {counts.at(index: 3)} {empty.first()}")
Output
Some(4) Some(7) None None

counts.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

steps/04-list-forms/src/shelf.unauna
  let receipt = empty.join(separator: ", ")
  @console.print("{counts.contains(item: 0)} {counts.sum()} '{receipt}'")
Output
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

steps/04-list-forms/src/shelf.unauna
  @console.print("{counts.sort()} {sizes.sort()}")
Output
[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:

steps/04-list-forms/src/shelf.unauna
  @console.print("{recount(counts, position: 1, counted: 5)} {counts}")
Output
[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: ==

steps/04-list-forms/src/shelf.unauna
  @console.print("{counts == [4, 0, 7]} {counts == [0, 4, 7]}")
Output
true false

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

src/shelf.unadiff
--- 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:

Diagnostic
[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:

steps/04-list-forms/src/shelf.unauna
  let shelf = [3, 1, 2]
  @console.print("{shelf.append(item: 1).sort()} {shelf.len}")
Show the answer
Output
[1, 1, 2, 3] 3

append 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.

Next:10.2 Functions as values, and lambdas