5. Collections and generics

Chapter 3 gave the receipt a category per row. The question a category invites is what each one comes to, and that needs somewhere to keep a running total per name, which is one of the two containers this chapter is about:

fn kind(name: str) -> str {
    match name {
        "tip" => "gratuity",
        "espresso" => "drink",
        _ => "food",
    }
}

kind is chapter 3’s, unchanged. The rest is the program, and both machines run it:

fn main() -> !int {
    let rows = """
        espresso,340
        pastry,275
        tip,100
        """
    var totals = Map[str, int]()
    for row in rows.lines() {
        var i = 0
        while row[i..i + 1] != "," { i += 1 }
        let k = kind(row[..i])
        let cents = row[i + 1..].to_int() else 0
        totals[k] = (totals[k] else 0) + cents
    }
    for (k, n) in totals.pairs() {
        print("{k:<10}{n:>5}")
    }
    0
}

$ wolf run totals.lu
drink       340
food        275
gratuity    100

One container, and one line of counting. totals[k] asks the Map for a category’s running total and answers none when there is no entry for k yet; else 0 reads that answer as zero, the way to_int() else 0 reads a field with no number in it; + cents adds the row; and totals[k] = … writes the sum back, inserting the entry on a category’s first row and replacing it on every row after. The Map answers “how much for this category”. What it does not promise is the order the categories showed up in: pairs() walks the entries in an order the language leaves unspecified, and §5.2, whose query needs that order, keeps it in a List.

5.1 List, Map, Set, tuples

A List[T] holds a sequence of T and grows at the end:

fn main() -> !int {
    var cents = List[int]()
    (mut cents).push(340)
    (mut cents).push(275)
    (mut cents).push(100)
    let last = (mut cents).pop()
    print("{cents.len} left, popped {last}, first {cents[0]}, empty {cents.is_empty()}")
    0
}

$ lupin list.lu
2 left, popped 100, first 340, empty false

List[int]() builds an empty one: the type in brackets, then the call. push appends, pop removes and returns the last element, len is the count, is_empty is the readable spelling of len == 0, and xs[i] reads the element at index i, counting from zero. push and pop both change the list they are called on, so every call arrives write-marked ((mut cents).push(340) is §3.1’s “this call writes cents”, in its natural habitat now), while len, is_empty, and xs[i] only read, and say nothing. Push and pop at one end also make a List the stack you reach for when a problem wants one.

A list whose elements you know as you write it is written out instead: [340, 275, 100] is the list those three pushes built, with the element type read off the elements. An empty literal has no element to read a type from, so it takes one from its binding, let names: List[str] = []; a bare let xs = [] is E0419, and the note spells the annotation for you. Everywhere else a [] finds its type on its own, as a call’s argument or a field’s value. Both machines run a list literal since lupin 0.1.37, which is why every block below that builds one is an ordinary two-machine run; until that release the interpreter answered [ with E0201 and these pages were compiled runs.

The brackets that read one element also take a range of them. Chapter 3 sliced strings; the same three endpoint spellings work on a List[T], for any T:

fn main() -> !int {
    var names = ["espresso", "pastry", "tip"]
    let rest = names[1..]
    let most = names[..^1]
    let _ = (mut names).pop()
    print("{names.len} {rest.len} {most.len}")
    print("{rest[0]} {most[0]} {names[0]}")
    0
}

$ wolf run names.lu
2 2 2
pastry espresso espresso

xs[1..] is everything after the first element, xs[..^1] everything but the last, xs[a..=b] an inclusive span — chapter 3’s spellings, unchanged. There is no rule making slices a string thing and indexing a list thing. One bracket surface, both containers on it.

One difference is worth the sentence, and it is why that program pops. A str slice is a view; a List slice is a copy. s[1..] looks at the original’s bytes and owns none of them; names[1..] allocates a fresh list in the ambient region and fills it. So names losing its last element on the next line leaves rest and most at two apiece: they stopped being about names the moment they were built. At the sizes in this book that copy costs nothing you can measure, which is exactly why it is worth knowing before you slice a list of a million.

That let _ = is the chapter’s one look at discarding a fallible value on purpose. pop answers T ! {none}; here the removal is the point and the element is not, and let _ = … says so where a reader can see it. Written bare as a statement instead, the same call is a dropped failure, and the compiler says so: W0601, this str ! {none} result is discarded, error row and all. Chapter 12 makes a rule of that; this is the spelling that satisfies it. A bare _ = … is not the spelling — E0201 on the compiler, unsupported on the interpreter — because _ on its own denotes no place.

A Map[K, V] associates keys with values:

fn main() -> !int {
    var totals = Map[str, int]()
    totals["drink"] = 340
    totals["food"] = 275
    totals["drink"] = (totals["drink"] else 0) + 100
    print("{totals.len} keys, drink {totals["drink"]}")
    for (k, n) in totals.pairs() {
        print("{k:<8}{n:>5}")
    }
    0
}

$ lupin map.lu
2 keys, drink 440
drink     440
food      275

m[k] = v puts a value in, m[k] reads it back, and pairs() walks the whole thing as key–value pairs, which the for destructures into two names. Two sentences about the read, which the rest of the chapter leans on. What m[k] answers is int ! {none}: the value when the key is bound and the mark none when it is not, so a Map is never asked to invent a number, and else 0 is how a running total reads a key it has not seen (§5.4 has the other half of that story). And a key is a str, an int, a char or a bool this edition, the four types whose equality the language itself defines, so the map can answer “is this the same key” without being told what sameness means. The same square brackets that carry the type at construction carry the key at use. The economy is deliberate, and §5.3 returns to it.

A tuple is a fixed group of values of possibly different types, written in parentheses and read by position:

fn split_at(row: str, i: int) -> (str, int) {
    (row[..i], row[i + 1..].to_int() else 0)
}
fn main() -> !int {
    let pair = split_at("espresso,340", 8)
    print("{pair.0} costs {pair.1}")
    let (name, cents) = split_at("tip,100", 3)
    print("{name} costs {cents}")
    0
}

$ lupin tuple.lu
espresso costs 340
tip costs 100

pair.0 and pair.1 are the elements; let (name, cents) = … takes them apart in one line. A tuple is how a function returns two things without either a struct nobody else will use or an output parameter, and (str, int) in the signature says exactly what comes back.

All three fit at the prompt, where the types are on the page:

wolf> var cents = List[int]()
wolf> (mut cents).push(340)
wolf> (mut cents).push(275)
wolf> cents.len
2 : i64
wolf> cents[0]
340 : i32
wolf> let pair = ("tip", 100)
wolf> pair.1
100 : i32
wolf> var totals = Map[str, int]()
wolf> totals["drink"] = 340
wolf> totals["drink"]
340 : i32
wolf> totals.len
1 : i64

A length is an i64 and an element is whatever the container holds, so cents.len and cents[0] print different types on adjacent lines. Chapter 1 met the same distinction with "wolf".len, and it holds at every container in the language.

That leaves Set, and the sentence about it is short: this edition’s std has no set container. Where a set is the right structure, the samples in Part 1 use a List and a linear scan, which is what seen_at does in §5.2. For the sizes in this book the scan costs nothing you can measure; for a set with ten thousand members a hashed set is the right structure.

Exercise 5-1 (fingers · lupin). A List is also a stack. Push three values, pop one, and print the popped value and the remaining length.

Exercise 5-2 (fingers · lupin). Score the pack: write two scores into a Map, raise one by reading it back, and print the table with format specs.

Exercise 5-12 (fingers · lupin). Histogram the word lengths of a two-line block, bars of # growing sideways, one row per length. A List[int] indexed by length is the whole data structure — grow it to fit as you go. One of your rows prints an empty bar. Which, and why does it print at all?

Exercise 5-14 (fingers · lupin). A comma-separated ledger, three rows of name,cents. Split each row, table it with format specs, and end with a total row. What does your program do with a row that has no comma, and which single spelling in your source decided that?

5.2 The combinator style

The program at the head of the chapter built a table. The first thing to ask of a table is a query, and the first query worth asking of this one is which two categories cost the most. A query has two spellings, and this section is about telling them apart.

The first spelling says what the result is: the table’s pairs, ordered by amount, first two.

totals.pairs().sorted_by(fn(a, b) b.1 <=> a.1).take(2)

Read left to right, every step names a result and none of them names a loop. That is the combinator style, and it is the spelling the language is designed for. This edition’s std ships one combinator, count(), and chapter 2 used it; a sort is not among them, so the line above is the shape of the answer and not a program this book runs.

The second spelling says how to make the result, and it is not the same program: the chain sorts all three categories, and the loop below never sorts. It picks the largest category not yet picked, twice. Two selections against one sort is the trade: for a top-2 of three, the selections are less work than ordering everything, and for a top-500 of ten thousand they are more. The loop is the spelling where the work itself is the thing you are choosing:

fn top(order: List[str], totals: Map[str, int], n: int) -> List[str] {
    var picked = List[str]()
    while picked.len < n {
        var best = ""
        for k in order {
            if seen_at(picked, k) < 0 {
                if best == "" || (totals[k] else 0) > (totals[best] else 0) { best = k }
            }
        }
        (mut picked).push(best)
    }
    picked
}

top reads all three of its parameters: order is the list it walks, totals is what it compares, and n is how many times it walks. Each pass finds the best category not already in picked; seen_at is the linear scan §5.1 promised, else 0 reads a total the way the head of the chapter wrote one, and best == "" means “nothing picked yet on this pass”, which is safe because no category is the empty string. The result is a new List, in the order the passes found things.

kind is the head of the chapter’s. seen_at answers “have I seen this string, and where”, and answers -1 for no:

fn kind(name: str) -> str {
    match name {
        "tip" => "gratuity",
        "espresso" => "drink",
        _ => "food",
    }
}
fn seen_at(xs: List[str], s: str) -> int {
    var i = 0
    while i < xs.len {
        if xs[i] == s { return i }
        i += 1
    }
    -1
}

And main, which is the head of the chapter’s with two lines changed. The query wants the categories in the order they arrived, which is the one thing the Map does not promise, so the loop keeps that order in a List beside the totals: seen_at asks the list whether a category is new, and the map counts as it did before. The last loop asks the query instead of printing the whole table. Both machines run it:

fn main() -> !int {
    let rows = """
        espresso,340
        pastry,275
        tip,100
        """
    var order = List[str]()
    var totals = Map[str, int]()
    for row in rows.lines() {
        var i = 0
        while row[i..i + 1] != "," { i += 1 }
        let k = kind(row[..i])
        let cents = row[i + 1..].to_int() else 0
        if seen_at(order, k) < 0 { (mut order).push(k) }
        totals[k] = (totals[k] else 0) + cents
    }
    for k in top(order, totals, 2) {
        print("{k:<10}{totals[k] else 0:>5}")
    }
    0
}

$ wolf run top2.lu
drink       340
food        275

The chain says what the result is; the loop says how to make it. Write the chain when it says what you meant, and the loop when the work is what you are choosing.

Exercise 5-6 (extension · wolf + lupin). Count lines the way the head of the chapter counted categories: a Map[str, int] and one line of counting per row. Then print each distinct line once, with its count, in the order the lines first appeared. The Map alone does not give you that order. Which container does, and why is it not the Map?

5.3 Generics in square brackets

seen_at searches a List[str]. The same three lines search a list of anything, and saying so takes one pair of brackets:

fn best[T](xs: List[T], better: fn(T, T) -> bool) -> T {
    var b = copy xs[0]
    var i = 1
    while i < xs.len {
        if better(xs[i], b) { b = copy xs[i] }
        i += 1
    }
    b
}
fn main() -> !int {
    let cents = [340, 275, 100]
    let names = ["espresso", "pastry", "tip"]
    print("{best(cents, fn(a, b) a > b)} {best[str](names, fn(a, b) a < b)}")
    0
}

$ wolf run best.lu
340 espresso

[T] after the name declares a type parameter: best works for any T, given a function that says which of two Ts wins. The two calls show both spellings (best(cents, …) lets the arguments determine T; best[str](names, …) names it), and naming it is documentation, because the arguments already pin it down.

copy is the second line’s whole story, and it is the word chapter 3 read out of the compiler’s help text. It is there because of what best does not know. Indexing a List[T] hands the element over, and for a T the definition knows nothing about the compiler assumes the worst: the element may be a str, or something else that must not be duplicated, so var b = xs[0] moves it out of the list. The list’s length survives that — xs.len belongs to the list, not to an element — but the loop’s xs[i] does not: an index that is not a literal may be 0, so it is the same place as the moved xs[0], and reading it is the E1001 chapter 3 met. And best was only lent xs, so handing b back as its answer would give the caller a second path to a value it still holds — E1002, chapter 7’s lend rule. The consequence is a refusal at compile time; no program observes a hole in the list, because no such program is built. Three errors, one cause, and the compiler prints the same repair under all three of them. copy takes a second value and leaves the list holding what it held, which is what a function that only inspects a list should do. A concrete list needs none of this: let c = cents[1] on a List[int] copies the word and leaves the list whole, because an int copies, and §5.1’s block read cents[0] in a hole and asked is_empty of the same list in the same line. What the copy costs is chapter 7’s subject; what it means here is that best reads its argument instead of consuming it. It is also the one thing best may do to a T without being handed the means: copy x produces an independent value from any type at all, granted by no bound and carried by no trait.

The interesting part is what best may do with a T. It compares them by calling the function you supplied, and it does not compare them with > itself, because it cannot: nothing is known about T at the definition. Try it anyway and the error arrives where the mistake is:

fn total[T](xs: List[T]) -> int {
    xs[0] + 1
}
fn main() -> !int {
    let xs: List[int] = []
    print("{total(xs)}")
    0
}

error[E0501]: the bounds on `T` say nothing about `+`
 --> ./s6.lu:5:5
  |
4 | fn total[T](xs: List[T]) -> int {
  |          - `T` is declared here
5 |     xs[0] + 1
  |     ^^^^^ `T` could be any type here
  |
  = note: add `T: Add` to the bound — `+` on a type parameter dispatches through `Add.add`
    ([type.trait.op]), and a generic body may use only what its bounds provide.
help: add the bound: `T: Add`
  |
4 | fn total[T: Add](xs: List[T]) -> int {
  |

Read the span. The error is on line 5 of total, in the file where total is written, not at the call. The definition promised to work for any T and then used a T in a way only some types allow, so the definition is wrong, and it is wrong whether or not anybody ever calls it with an int. A generic function in a library you publish is checked once, by you, not rediscovered by everyone who instantiates it. The note and the help: under it name the repair, a bound on T, and §5.6 is where that repair is made.

Why [] and no turbofish. Map[str, int] and totals["drink"] use the same brackets, and so do best[str](names, …) and xs[i]. Rust writes HashMap<String, i32> and then, when an expression is ambiguous, parse::<i32>(), the turbofish, which exists because < is also less-than and the parser cannot tell a generic argument from a comparison without help. Wolf’s grammar has no such ambiguity to resolve, because e[…] parses as one postfix form and the question of index-versus-type-argument is settled later, by the part of the compiler that knows what e is. The cost is paid once, in the compiler’s grammar–semantics seam, instead of at every call site. The bet is that the seam’s diagnostics stay good enough that the reader never learns it exists, and this book will hold the compiler to that bet.

The fn(T, T) -> bool parameter is a teaching choice; a trait could name the comparison, and §5.6 writes best again with the function gone and a bound in its place. The parameter stays here because it keeps the rule visible: what best may do with a T is exactly what you hand it the means to do.

Exercise 5-3 (extension · lupin). Write first[T] with a fallback for the empty case, and call it twice: once with the type named, once letting inference name it. Read the element rather than removing it: pop answers T ! {none} and changes the list it is called on, and a function that changes its argument is chapter 7’s mut, at both ends of the call. Then write its partner rest[T], everything after the first element. The intended spelling is the slice from §5.1 — xs[1..], one line — and not a loop that pushes elements into a new list one at a time. first needed a fallback for the empty list; find out what rest needs by running xs[1..] on one, and say which of the two exercises has the harder empty case.

Exercise 5-5 (design). Wolf writes generics top[T] and indexing m["k"] with the same brackets. Rust chose ::<T> partly to avoid that ambiguity. What does wolf’s choice cost, and where is the cost paid?

5.4 Indexing that traps

Chapter 2’s slices were checked. So is every index in this chapter:

fn main() -> !int {
    var cents = List[int]()
    (mut cents).push(340)
    print("{cents[0]}")
    print("{cents[1]}")
    0
}

$ lupin index.lu
340
index.lu: trap(bounds): index 1 is outside a collection of 1 element(s) [mem.ub.defined] at 5:13
$ echo $?
3

One element, indexes 0 and 1 attempted, and the second one ends the program: same trap kind and same clause as a string slice off the end, because it is the same rule about the same kind of mistake. There is no index that returns a garbage element and no negative index that counts from the back: cents[-1] traps too, reporting index -1.

pop is the other shape. An empty list is not a mistake to fault on, it is a question with an answer, so pop hands back int ! {none} and the answer is none:

fn main() -> !int {
    var cents = List[int]()
    let v = (mut cents).pop()
    print("{v}")
    0
}

$ lupin pop.lu
none
$ echo $?
0

pop, get, first and last all read this way: each answers the element or the mark none, and none of the four faults on any input. The subscript is the faulting twin — cents[0] on an empty list traps, because an index the program computed and got wrong is a different event from a lookup that came up empty. Ask is_empty first when the distinction matters, and let else read the mark when it does not (chapter 6’s subject).

One index in the language never traps, and it is a Map key. Both machines run this one:

fn main() -> !int {
    var totals = Map[str, int]()
    totals["drink"] = 340
    print("[{totals["tip"]}]")
    0
}

$ wolf run absent.lu
[none]

none is what a lookup answers for a key that is not there: not a trap, not a zero, and not a refusal. It is pop’s answer on an empty list, for pop’s reason: an index the program computed and got wrong is a mistake, and a key that happens not to be bound is a question, so m[k] is int ! {none} and never faults. What the mark rules out is counting up from an absence by accident. m[k] += v would have to read a value that may not exist, and the compiler refuses it where it is written:

fn main() -> !int {
    var totals = Map[str, int]()
    totals["drink"] += 340
    0
}

error[E0417]: cannot update `totals["drink"]` in place: the key may be absent
 --> ./s10.lu:6:5
  |
6 |     totals["drink"] += 340
  |     ------ `totals` is a `Map`
  |     ^^^^^^^^^^^^^^^ a `Map` index is a row, not a place
  |
  = note: `m[k]` is `V ! {none}` ([mem.map.absent]): reading it asks whether the key is bound, and
    an absent key has no value to update. `m[k] = v` alone inserts or replaces.
  = note: spell the two halves — `totals["drink"] = (totals["drink"] else 0) + …` — or count with
    std's named operation, `map.tally(mut totals, k)` (`use std.map`), which is that
    statement for an `int`-valued map.

The first note is the rule and the second is the spelling this chapter has used from its first program: read with a default, then write the sum. m[k] = v on its own is legal on any key, inserting when the key is absent and replacing when it is bound, which is why the write half never needs a branch. One line where a lookup and a guess would do is the price of being explicit about absence, and a missing key is an answer with a type.

What the machine does. A List is a pointer, a length, and a capacity: push writes at the end and doubles the buffer when it runs out, which makes the cost of n pushes proportional to n even though individual pushes occasionally copy. xs[i] is an address computation and a comparison: the bounds check is the comparison, and the same analysis that hoists arithmetic checks out of loops hoists these when the range is provable. None of these operations copies the elements: pairs() hands out views, pop hands the element over the way §4.4’s returns do. Which is why seen_at’s linear scan costs one comparison per element and nothing else, and why the objection to it is the number of comparisons, not the copying.

Exercise 5-4 (comprehension · lupin). The list has one element. Predict xs[10], precisely: what kind of event, and what exit code.

Exercise 5-7 (fingers + extension · lupin). A grade book. The block below has one name,score line per student. Parse it into two lists side by side, a List[str] of names and a List[int] of scores, with to_int() else 0 reading each score, then print the top scorer’s name and score using §5.3’s best with a comparison function (best(scores, fn(a, b) a > b)), the class average to the nearest whole point, and each student on their own line with above or below beside the average. Then §5.4’s question: what does your program do on an empty block, and which line traps first? Guard it so an empty block prints one sentence and exits 0.

ada,91
grace,78
linus,84
mira,69

5.5 Structs

§5.1’s split_at answered a tuple, (str, int), and the caller took it apart on the next line. A tuple is the right shape for exactly that: a group of values handed over once and opened at once. The receipt’s row is a different kind of group. It is built in one place and read in three, and a reader of pair.1 has to remember what the second position holds. A struct is the tuple with names:

struct Row { kind: str, cents: int }
fn text(r: Row) -> str { "{r.kind:<10}{r.cents:>5}" }
fn main() -> !int {
    let first = Row { kind: "drink", cents: 340 }
    var tip = Row { kind: "gratuity", cents: 100 }
    tip.cents += 20
    print(text(first))
    print(text(tip))
    print("{first.kind} and {tip.kind}, {first.cents + tip.cents} in all")
    0
}

$ lupin row.lu
drink       340
gratuity    120
drink and gratuity, 460 in all

Four things on the page, one line each. The declaration, struct Row { kind: str, cents: int }, names the type and its two fields, each a name and a type, and it is the whole definition: no constructor, no method, nothing to import. The literal, Row { kind: "drink", cents: 340 }, builds one and names every field as it does; the compiler refuses a literal that leaves a field out, where it is written, because a Row with no cents is not a Row. The field read, r.kind, is the tuple’s pair.0 with the position spelled as a word, and it reads through any binding, including the parameter r inside text. And the field write, tip.cents += 20, is why tip is a var: a field is a place inside the value it belongs to, so writing the field changes the value, and var is chapter 3’s spelling for a name whose contents change. first is read and never written, so it is a let.

text(first) hands the struct to a function and main reads first.kind on the line after, the way §5.3’s best read its list and left it whole. A parameter with nothing written in front of it is read for the call and returned to the caller as it was, and what text may do with a Row is exactly what main may do: read r.kind, read r.cents, build a string from them. The format specs are §5.4’s, so text prints the line the head of the chapter printed, from a value instead of from two loose names.

When to reach for which is the one judgment this section asks of you. A tuple is right when the group is opened as soon as it arrives and travels no further: split_at’s answer is consumed by the let (name, cents) on the next line, and a name for that pair would be a name nobody reads twice. A struct is right when the group has a life of its own, built here and read there, because the word on the field is what a reader three functions away sees. Names earn their keep the moment a value travels.

Exercise 5-16 (fingers · lupin). Respell §5.1’s split_at to answer a Row instead of a (str, int), and use it to parse the three rows at the head of the chapter and print them through text. One line of the caller gets shorter and one line of the function gets longer. Name both, and say what each reader gained.

Exercise 5-17 (extension · lupin). A struct holds a list as easily as an int. Declare Receipt { rows: List[Row] }, build one from the three rows, and write total(r: Receipt) -> int as a plain function with no impl. Print the count of rows and the total. Then read total’s signature and say what it tells a caller about r.rows: does the call change the list, and which character on the line says so?

5.6 Traits

§5.3 wrote total[T] and the compiler refused it: the bounds on T say nothing about +. Read the note under that refusal again, because it names the repair. Add T: Add to the bound. A bound is what a generic function is allowed to assume about its T, and + is granted by a trait called Add. So this is the section generics owed you. A trait names a capability, an impl says a type has it, and a bound says a generic body may use it:

trait Add {
    fn add(self, other: Self) -> Self
}
impl Add for int {
    fn add(self, other: Self) -> Self { self + other }
}
impl Add for f64 {
    fn add(self, other: Self) -> Self { self + other }
}
fn total[T: Add](xs: List[T], zero: T) -> T {
    var acc = copy zero
    for x in xs { acc = acc + x }
    acc
}
fn main() -> !int {
    let cents: List[int] = [340, 275, 100]
    let dollars = [3.5, 2.25]
    print("{total(cents, 0)} {total(dollars, 0.0)}")
    0
}

$ wolf run total.lu
715 5.75

Read the three parts top to bottom. trait Add declares one method, add, whose receiver and other operand are both Self, the type doing the implementing, and whose answer is a Self as well. impl Add for int says an int has that capability and spells it as the builtin +; impl Add for f64 says the same for a float. fn total[T: Add] is §5.3’s function with the bound written in, and the bound is what changed the verdict: acc + x on a T is Add.add(acc, x), the same call by another spelling, and the definition is checked once against exactly that. At int the call runs the int impl and the machine adds two words; at f64 it runs the other one. total is written once, proven once, and instantiated twice, with zero telling each instantiation where to start.

And copy zero is not decoration. A parameter written without a mode is a read: the caller lends its value for the call and still owns it afterwards. var acc = zero would move that lent value into acc, and acc is what the function returns — a second live path to something the caller still holds, which is [mem.tier0.mode.read] and E1002. The copy says what the accumulator actually wants: start from a value of my own. For an int or an f64 it costs nothing, because a value that reaches no heap storage is its own copy. The compiler began enforcing this at wolf 0.2.15, and it is the same rule §5.3 met from the other side: a generic body is checked once for every T, so the spelling has to be right for the T that allocates as well as the one that does not.

One annotation in main is spelled out, List[int], and the program runs without it. An integer literal with nothing to decide it is an i32 ([type.numlit.default]), but a bound is context: these literals reach total only through T: Add, the impls above are for int and not i32, so the literals take int, and the list written bare prints the same 715. The float list needs no annotation for the plainer reason that a float literal’s default is the f64 its impl names. Every bounded call in this section spells its integer list anyway, so the type the bound settles is on the page.

Two things the block does not do. self + other inside the int impl does not call add again: an operator on two primitives is the builtin operation whatever impls are in scope, which is what makes the impl the floor of the dispatch and not another step of it. And total still cannot compare or multiply a T, because the bound grants Add and nothing else; a body that reaches for * under this bound is refused at the definition with the same E0501, and its note names Mul.

A trait is also how two types share a name. The receipt has rows and it has a header, and both want to put themselves on a line:

struct Row { kind: str, cents: int }
struct Header { title: str }
trait Line {
    fn text(self) -> str
    fn framed(self) -> str { "| {self.text()} |" }
}
impl Line for Row {
    fn text(self) -> str { "{self.kind:<10}{self.cents:>5}" }
}
impl Line for Header {
    fn text(self) -> str { "{self.title:<15}" }
}
fn main() -> !int {
    let h = Header { title: "receipt" }
    let r = Row { kind: "drink", cents: 340 }
    print(h.framed())
    print(r.framed())
    0
}

$ lupin lines.lu
| receipt         |
| drink       340 |

Line declares text with no body, so every implementing type must supply one, and it declares framed with a body, a default, so no implementing type has to. The default calls self.text(), and the call dispatches through the implementing type: r.framed() runs Row’s text inside Line’s framed, and h.framed() runs Header’s. That is the whole mechanism, and it is the one total used a page ago. A trait names the capability, impl Line for Row claims it for Row, and the compiler checks the claim where the impl is written, so an impl that forgets text is refused at the impl line and never at a call. It is §5.3’s definition-site rule applied to a type instead of a function. self is the receiver, written first in each method’s parameter list, and r.text() is the ordinary way to call one; §5.5’s free function text(r) did the same job without a trait, and the difference is that framed can now be written once for every type that has a text.

Comparison is a capability too. == on two ints is the machine’s; on two Rows it is whatever Row’s Eq says, because an operator whose left operand is a struct dispatches through the trait of the operator’s name, the way + on a T did. Nothing is assumed on the type’s behalf: a struct with no impl Eq does not compare, and the compiler refuses the == where it is written. Both machines run it:

struct Row { kind: str, cents: int }
trait Eq {
    fn eq(self, other: Self) -> bool
}
impl Eq for Row {
    fn eq(self, other: Self) -> bool { self.kind == other.kind }
}
fn main() -> !int {
    let a = Row { kind: "drink", cents: 340 }
    let b = Row { kind: "drink", cents: 275 }
    let c = Row { kind: "food", cents: 275 }
    print("{a == b} {a == c} {b != c}")
    0
}

$ wolf run eq.lu
true false true

Row’s Eq compares kinds and ignores cents, so a == b is true for two rows that differ in every byte of their second field. That is the impl being consulted, and it is the point: what makes two Rows the same is a decision the type makes, spelled once, in the one place a reader looks. != is the negation of the same call, and the comparison operators read an Ord the same way, which is the next block. Two rules keep this from surprising you. The operator reaches for the trait of its own name, so the trait has to be called Eq and its eq has to have the shape above. And an operator on two primitives is never redirected, so self.kind == other.kind inside the impl compares two strs the way chapter 2 did.

Eq answers a bool. Ord answers which of three things is true, and that takes a type with exactly three values. §5.3’s best took a comparison function because nothing was known about its T; with a bound, the function goes:

enum Ordering { Less, Equal, Greater }
trait Ord {
    fn cmp(self, other: Self) -> Ordering
}
impl Ord for int {
    fn cmp(self, other: Self) -> Ordering {
        if self < other { Ordering.Less } else if self == other { Ordering.Equal } else { Ordering.Greater }
    }
}
impl Ord for str {
    fn cmp(self, other: Self) -> Ordering {
        if self < other { Ordering.Less } else if self == other { Ordering.Equal } else { Ordering.Greater }
    }
}
fn best[T: Ord](xs: List[T]) -> T {
    var b = copy xs[0]
    var i = 1
    while i < xs.len {
        if xs[i] > b { b = copy xs[i] }
        i += 1
    }
    b
}
fn main() -> !int {
    let cents: List[int] = [340, 275, 100]
    let names = ["espresso", "pastry", "tip"]
    print("{best(cents)} {best(names)}")
    0
}

$ wolf run best.lu
340 tip

enum Ordering { Less, Equal, Greater } declares a type with three values and no others, each named through the type, Ordering.Less. trait Ord has one method, cmp, and its answer is one of the three. The two impls spell it with the builtin comparisons, which is the floor once more: self < other on two ints is the machine’s. fn best[T: Ord] is §5.3’s best with the bound where the function parameter was, and xs[i] > b on a T is Ord.cmp(xs[i], b) read against the answer. < is cmp answering Less, > is Greater, <= is anything but Greater, >= is anything but Less, and <=> is the Ordering itself, for a match to read. One trait, five operators. The two calls run the two impls, and best is now the function §5.3 said a trait could make it: nothing is handed in, because the bound hands it the means.

Not every operator has two operands. Prefix - reads one, and its trait, Neg, declares a method with only a receiver:

struct Row { kind: str, cents: int }
trait Neg {
    fn neg(self) -> Self
}
impl Neg for int { fn neg(self) -> Self { -self } }
impl Neg for f64 { fn neg(self) -> Self { -self } }
fn refund[T: Neg](charged: T) -> T { -charged }
fn main() -> !int {
    let r = Row { kind: "drink", cents: 340 }
    let tip = 0.75
    print("{refund(r.cents)} {refund(tip)}")
    0
}

$ lupin refund.lu
-340 -0.75

-charged on a T is Neg.neg(charged), and a refund is the receipt’s own use for it: the row was charged, and the same amount goes back the other way. -self inside the int impl is the builtin negation, so the impl is the floor and not a loop, the rule the Add impl followed.

A bound is a list. + between trait names says the body may use everything each of them grants, and the receipt has a function that needs two:

enum Ordering { Less, Equal, Greater }
trait Add {
    fn add(self, other: Self) -> Self
}
trait Ord {
    fn cmp(self, other: Self) -> Ordering
}
impl Add for int { fn add(self, other: Self) -> Self { self + other } }
impl Ord for int {
    fn cmp(self, other: Self) -> Ordering {
        if self < other { Ordering.Less } else if self == other { Ordering.Equal } else { Ordering.Greater }
    }
}
fn capped[T: Add + Ord](xs: List[T], zero: T, cap: T) -> T {
    var acc = copy zero
    for x in xs { acc = acc + x }
    if acc > cap { copy cap } else { acc }
}
fn main() -> !int {
    let cents: List[int] = [340, 275, 100]
    print("{capped(cents, 0, 500)} {capped(cents, 0, 1000)}")
    0
}

$ wolf run capped.lu
500 715

capped totals the rows and stops at a ceiling, a receipt with a spending limit on it. acc + x reaches through Add and acc > cap through Ord, in one body, under one bound that names both. Drop either name from the bound and the line that needed it is refused at the definition with the E0501 §5.3 met, its note naming the missing trait; and every type capped is instantiated at must implement both, checked at the call by name, which is the refusal this section ends on.

Two things no bound grants, so that the list of what one can grant is complete. copy needs none: §5.3 used it on a bare T, and it is the one operation every type carries. And three operators have no trait at all. && and || are bool’s alone, and ! is bool’s logical not and an integer’s bitwise complement (§2.3) and nothing else’s, so a body that writes x && y or !x on a T is refused at the definition with a note that says so in the compiler’s words: no trait covers this operator: !, && and || are bool‘s and the bitwise operators are the integers’ alone this edition; take a concrete type here (E0501; the note’s “! … bool’s” predates ! on integers, and its point stands: no bound can grant either meaning). The rule under all of it is §5.3’s: a generic body may use only what its bounds provide, and a parameter with no bound provides nothing, not even a method call. Chapter 11 takes a scope handle as a bare [S] and calls s.spawn(…) on it; the compiler refuses that call by this rule, and that chapter says why the page keeps it.

std’s arithmetic bound is not Add alone. It is Num, and Num is an alias, a name that stands for a list of traits:

trait Add {
    fn add(self, other: Self) -> Self
}
trait Eq {
    fn eq(self, other: Self) -> bool
}
trait Num = Add + Eq
impl Add for int { fn add(self, other: Self) -> Self { self + other } }
impl Eq for int { fn eq(self, other: Self) -> bool { self == other } }
fn total[T: Num](xs: List[T], zero: T) -> T {
    var acc = copy zero
    for x in xs { acc = acc + x }
    acc
}
fn main() -> !int {
    let cents: List[int] = [340, 275, 100]
    print("{total(cents, 0)}")
    0
}

$ wolf run num.lu
715

trait Num = Add + Eq declares no methods. It names the list once, so that [T: Num] says what [T: Add + Eq] says without spelling the list at every function: total’s body may use + through Add and == through Eq, and every type total is instantiated at must implement both. std spells the real one as trait Num = Add + Sub + Mul + Div + Rem + Eq + Ord, the five arithmetic traits and the two comparison traits, so that a function bounded by Num can do arithmetic and can sort. An alias is never implemented (you implement its members, and impl Num for int is refused), and nothing about it is checked in bulk: the compiler reads the list and checks each name. Which is what the last block shows. f64 here has an Add and no Eq:

trait Add {
    fn add(self, other: Self) -> Self
}
trait Eq {
    fn eq(self, other: Self) -> bool
}
trait Num = Add + Eq
impl Add for f64 { fn add(self, other: Self) -> Self { self + other } }
fn total[T: Num](xs: List[T], zero: T) -> T {
    var acc = copy zero
    for x in xs { acc = acc + x }
    acc
}
fn main() -> !int {
    let dollars = [3.5]
    print("{total(dollars, 0.0)}")
    0
}

error[E0502]: `f64` does not implement `Eq`, which `total` requires of `T`
  --> ./s19.lu:19:28
   |
12 | fn total[T: Num](xs: List[T], zero: T) -> T {
   |             --- the bound is declared here
...
19 |     print("{total(dollars, 0.0)}")
   |                            ^^^ this is `f64`
   |
   = note: write `impl Eq for f64` in the trait's module or the type's module — or, when both are
     foreign, adapt: `type Local = distinct f64` and implement the trait for the adapter.

The refusal is at the call and it names Eq. total itself is fine, proven once at its definition against everything Num lists; this instantiation is what fails, and the trait named is the missing one, never the alias, so the repair is one impl and the message says which. The same reading holds for a bound of seven: a type that has six of them is refused by the name of the seventh.

Exercise 5-18 (design). The alias Num names seven traits, and a call under [T: Num] is checked against each of them by name. Why does the refusal name the missing trait and never the alias? Say what a reader would lose if it read “f64 is not a Num”, and what the author of a seven-trait alias gains from the compiler never mentioning it.

Exercise 5-11 (extension · lupin). Exercise 2-7 encoded runs with byte slices; a coder without a decoder is half a tool. Respell encode over chars(), growing the output with "{prev}{run_len}", then write decode, and round-trip both "wwwwoooolf" and a string whose runs reach two digits. Make main exit nonzero on any mismatch, so the round trip is a check the machine performs rather than a claim. Where in decode does the two-digit case live?

Exercise 5-13 (extension · lupin). Write any_index(s, set): the byte index in s of the first character that appears in set, or −1 for none. Probe it with a vowel set against a line that has vowels, one that does not, and the empty string. Why do the last two answers have to be the same, and what would distinguishing them cost your callers?

Exercise 5-15 (extension · lupin). Fold a long line at twelve columns: greedy fill, words never split, each output line as full as the width allows. Return the lines as a List[str] and print them. One comparison in your loop encodes the whole policy — which one, and what single change makes ragged-right into one-word-per-line?