Code for any type: generics

Since lesson 7.1, the arithmetic behind /last has lived inside one arm of main's big match, written for the history: a list of Message. "The last n items" is a useful idea far beyond messages, though. Here it is pulled out into functions, for a list of words and for a list of numbers.

$ cargo run
["is", "fun"]
[4, 1, 5]

One new method first: saturating_sub(n) subtracts, but stops at zero instead of going below it. Asking for the last 5 of 3 items gives a start of 0, which means "everything". It is the if n >= history.len() { 0 } else { ... } from lesson 7.1 in one word.

Now look at the two bodies. They are identical, character for character. Only the type in the first line differs. And the bodies never look at an item: they count items and cut the slice at a position. Whatever the items are, the work is the same. Writing it twice is not just tedious; the day you fix a mistake in one copy, the other keeps it.

So write it once, and leave the type blank:

$ cargo run
["is", "fun"]
[4, 1, 5]

<T> after the name declares a type parameter: a placeholder name for "some type, which whoever calls the function chooses". Read the first line out loud as: for any type T, last_n takes a slice of T and a count, and gives back a slice of T. T is only a name, by custom a single capital letter. A function with a type parameter is called generic.

You never say what T is. At each call, the compiler looks at what you passed: &words is a slice of String, so here T is String and the answer is a slice of String too. It works this out for you, the same way it works out the type of a let.

Look back at the types you have written since chapter 6. Vec<Message>, Option<String>, Result<usize, CommandError>, HashMap<String, String>. The angle brackets were type parameters every time. The standard library wrote Vec<T> once, "a growable list of T", and you filled in the blank: Message. Option<T> is "a T, or nothing". Result<T, E> has two blanks, one for success and one for the reason, and HashMap<K, V> has two, the key and the value.

Even "3".parse::<u32>() from lesson 7.1 was this: parse is generic, and ::<u32> fills in its blank by hand because nothing else in the line says which number type you want. You can do the same with your own: last_n::<u32>(&[], 3).

There is a catch, and it is what keeps generics honest. Inside last_n, the compiler does not know what T will be. So the body may only do with a T what works for every possible type. Holding one, moving it, lending it: fine. Adding two together? Not every type can be added. Predict.

error[E0369]: cannot add `T` to `T`
 --> src/main.rs:2:7
  |
2 |     a + b
  |     - ^ - T
  |     |
  |     T
  |
help: consider restricting type parameter `T` with trait `Add`
  |
1 | fn total<T: std::ops::Add<Output = T>>(a: T, b: T) -> T {
  |           +++++++++++++++++++++++++++

The same happens with comparing. Here is a function that should return the bigger of two values, for numbers and for words alike, and what the compiler makes of it.

error[E0369]: binary operation `>` cannot be applied to type `T`
 --> src/main.rs:2:10
  |
2 |     if a > b { a } else { b }
  |        - ^ - T
  |        |
  |        T
  |
help: consider restricting type parameter `T` with trait `PartialOrd`
  |
1 | fn bigger<T: std::cmp::PartialOrd>(a: T, b: T) -> T {
  |            ++++++++++++++++++++++

The part after the colon, T: PartialOrd, is a bound: a condition on which types may fill the blank. PartialOrd and Display are traits, named abilities a type can have. The very next lesson is about traits, including how to give your own types an ability. For now, here is one more bound in action. This function prints any list, as long as its items can be printed:

$ cargo run
- /help
- /last 3
- 2.5
- 0.5

A program that runs does not have blanks in it. So what happens to last_n? When the compiler builds Chatterbox, it sees every call and every type T is used with, and for each one it writes a separate copy of the function with T filled in, exactly as if you had written them by hand: a last_n for Message, one for u32, and so on. You wrote the two functions at the top of this lesson once; the compiler wrote them for you. The name for this is monomorphisation, from Greek for "making into one shape".

Why a copy per type, and not one shared function? Look at &items[start..]. To find where item number start begins, the machine multiplies start by the size of one item. The slice itself is the same size for every T, as the inspector shows, but the items it points at are not:

Each copy has the right item size built in, so each is exactly as fast as one you would have written by hand. Generics cost nothing while the program runs. What they do cost is paid earlier: a little more work for the compiler, and a slightly bigger program, one copy per type you actually use.

Chatterbox gets last_n exactly as you have seen it, in main.rs under reply, with a /// comment explaining the <T>. The /last arm shrinks from nine lines to a loop over last_n(&history, n): here T is Message. The if that guarded against subtracting below zero is gone, because saturating_sub does that job.

The new test, last_n_takes_from_the_end, calls it with numbers and with words, never with a message at all. That is the point of a generic function: it can be tested on the simplest types there are and trusted on the rest. In the run, /last 1 shows the bot's last answer, and /last 0 shows nothing, since zero items is a perfectly good answer.

Sam
one
two
/last 1
/last 0
/quit

Chatterbox v0.8
What should I call you?
Hi Sam! I'm Chatterbox. Ask me anything.
bot: you said: one
bot: you said: two
bot: you said: two
bot: bye, Sam!
messages so far: 2
saved 4 messages to chatterbox.log

Sources The Rust Book: Generic Data Types · The Rust Book: Traits as bounds · Rust error index: E0369 · usize::saturating_sub