5. Collections and generics without fear

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 — one of the two containers this chapter is about, plus a list to remember the order the categories arrived in:

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
    }
    0 - 1
}

kind is chapter 3’s, unchanged. seen_at answers “have I seen this category, and where” with the linear scan §5.1 will have a word about. The rest is the program:

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 {
            order.push(k)
            totals[k] = cents
        } else {
            totals[k] += cents
        }
    }
    for k in order {
        print("{k:<10}{totals[k]:>5}")
    }
    0
}

$ lupin totals.lu
drink       340
food        275
gratuity    100

Two containers, one job each: the Map answers “how much for this category”, the List answers “in what order did the categories show up”. Neither answers the other’s question well, which is the honest version of choosing a data structure.

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]()
    cents.push(340)
    cents.push(275)
    cents.push(100)
    let last = 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 at one end also make a List the stack you reach for when a problem wants one.

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

fn main() -> !int {
    var totals = Map[str, int]()
    totals["drink"] = 340
    totals["food"] = 275
    totals["drink"] += 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, m[k] += v updates it in place, and pairs() walks the whole thing as key–value pairs, which the for destructures into two names. The same square brackets that carry the type at construction carry the key at use, which is a deliberate economy and §5.3’s subject.

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> cents.push(340)
wolf> 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 — the distinction chapter 1 met with "wolf".len, holding at every container in the language.

That leaves Set, and here the book has to be honest: the pinned interpreter has not got one.

fn main() -> !int {
    var kinds = Set[str]()
    kinds.add("drink")
    print("{kinds.len}")
    0
}

$ lupin set.lu
set.lu: unsupported: `str` does not resolve
$ echo $?
4

Exit 4 is the interpreter declining the program rather than running it, and the message blames the element type rather than the missing container. Where a set is the right structure in Part 1, the samples use a List and a linear scan, which is what seen_at is doing in the program at the head of this chapter. For the sizes in this book that costs nothing you can measure; for a set with ten thousand members it is the wrong answer, and a hashed set is the right one.

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.

5.2 The combinator style

Here is what the top category ought to look like. It is the spelling the language is designed for, from the program that started wolf’s syntax argument:

fn main() -> !int {
    var totals = Map[str, int]()
    totals["drink"] = 440
    totals["food"] = 275
    for (k, n) in totals.pairs().sorted_by(fn(a, b) b.1 <=> a.1).take(1) {
        print("{k} {n}")
    }
    0
}

Read it left to right: take the pairs, sort them by the second element descending, keep the first. Every step names a result and none of them names a loop; <=> compares two values and answers −1, 0, or 1, which is all sorted_by needs from you.

Now run it:

$ lupin chain.lu
chain.lu: unsupported: `List` has no method `sorted_by` in this machine's std subset
$ echo $?
4

None of the combinators exist yet — not sorted_by, not take, not map, filter, or sum. What does exist is the thing they are all built from: an iterator, a value that yields elements one at a time, which is what lines(), words(), and pairs() return and what for consumes. count() is the one combinator in the subset, and chapter 2 used it.

So the section’s promise arrives in the honest order. Instead of writing the chain and then desugaring it for understanding, we write the desugaring because it runs, and keep the chain on the page as the thing it is a translation of:

fn seen_at(xs: List[str], s: str) -> int {
    var i = 0
    while i < xs.len {
        if xs[i] == s { return i }
        i += 1
    }
    0 - 1
}
fn totals_of(order: List[str]) -> Map[str, int] {
    var totals = Map[str, int]()
    totals["drink"] = 440
    totals["food"] = 275
    totals["gratuity"] = 100
    totals
}

Three categories with their totals, standing in for the receipt’s, and the ranking itself:

fn main() -> !int {
    var order = List[str]()
    order.push("drink")
    order.push("food")
    order.push("gratuity")
    let totals = totals_of(order)
    var taken = List[str]()
    while taken.len < 2 {
        var best = ""
        for k in order {
            if seen_at(taken, k) < 0 {
                if best == "" || totals[k] > totals[best] { best = k }
            }
        }
        print("{best:<10}{totals[best]:>5}")
        taken.push(best)
    }
    0
}

$ lupin top2.lu
drink       440
food        275

Fifteen lines against one, and they are not the same program: the loop version never sorts. It walks the categories twice looking for the largest not yet printed, which for a top-2 is strictly less work than ordering everything — and for a top-500 is strictly more. That is the trade the combinator style makes on purpose. The chain states the shape of the result and lets the library pick the work; the loop states the work and leaves the reader to infer the shape. When both spell the same answer, prefer the one that says what you meant, and reach for the loop when the work is the thing you are choosing.

Exercise 5-6 (extension · lupin) — uniq counts adjacent duplicates; yours will count all of them and keep first-seen order. Read a multiline block line by line and print each distinct line once, with its count, in the order lines first appeared. Two parallel lists — one of lines seen, one of counts — are enough. Why does a Map alone not solve this?

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 = xs[0]
    var i = 1
    while i < xs.len {
        if better(xs[i], b) { b = xs[i] }
        i += 1
    }
    b
}
fn main() -> !int {
    var cents = List[int]()
    cents.push(340)
    cents.push(275)
    cents.push(100)
    var names = List[str]()
    names.push("espresso")
    names.push("pastry")
    names.push("tip")
    print("{best(cents, fn(a, b) a > b)} {best[str](names, fn(a, b) a < b)}")
    0
}

$ lupin 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 rather than a requirement, because the arguments already pin it down.

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 `+`
 --> ./s7.lu:5:5
  |
5 |     xs[0] + 1
  |     ^^^^^ `T` could be any type here
  |
  = note: bounds grant trait members only, and no trait covers this operator yet (operator traits
    are a later sprint); take a concrete type here, or dispatch through a trait method.

Read the span. The error is on line 5 of total, in the file where total is written — not at the call, and not in a wall of text about List[int]. 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. That is the pitch: your mistakes are caught where you made them. A generic function in a library you publish is checked once, by you, rather than rediscovered by everyone who instantiates it.

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 real and somebody pays it: it is paid once, in the compiler’s grammar–semantics seam, instead of forever, in user code. 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.

No traits yet, either here or in what best demands of T — the fn(T, T) -> bool parameter is standing in for a comparison trait that lands with the trait system. The error above says as much in its own note, which is the compiler being honest about its own schedule.

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.

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]()
    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 104..112
$ 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[0 - 1] traps too, reporting index -1.

pop is bounds-checked for the same reason:

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

$ lupin pop.lu
pop.lu: trap(bounds): `pop` on an empty List [mem.ub.defined] at 60..71
$ echo $?
3

A stack that hands you something when it is empty is a stack that turns one bug into two, twenty lines apart. Ask is_empty first — or, when a caller can do something better with the news than dying, hand the emptiness back as a value, which is chapter 6.

One index in the language is not checked, and it is a Map key:

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

$ lupin absent.lu
[()]

() is what a lookup yields for a key that is not there — not a trap, not a zero, and not a refusal. It is also nearly unusable: put it in arithmetic and the run stops.

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

$ lupin bump.lu
bump.lu: unsupported: `totals["tip"]` does not denote a place at run time
$ echo $?
4

So a Map in Part 1 is written the way the program at the head of this chapter writes it: decide whether the key is new, then insert or update deliberately. Two branches where one lookup would do is the price of being explicit about absence, and being explicit about absence is the habit the rest of the book rewards — a missing key is an answer, and an answer belongs in the type system rather than in a convention about zero.

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. What none of these operations do is copy 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 honest 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 (comprehension + extension · lupin) — An RPN evaluator is a loop and a stack, and the stack is a List. Given the tokens 3 4 + 2 *, trace the stack contents after each token on paper, then run. Then answer from your trace, not from the code: which input would make stack.len < 2 true at an operator, and what does your evaluator do about it?