Generics, written once

You have written this function before, in some language, more than once. You wrote it to find the largest number in a list. Then a different list came along, a list of letters this time, and the sensible thing was the fastest thing: copy the function, change i32 to char in two places, and move on. Now there are two functions whose bodies are character for character identical except for a type. Read them, then press Run:

// The same logic twice, once per type. This is the problem generics solve.
fn largest_i32(items: &[i32]) -> i32 {
    let mut best = items[0];
    for &item in items {
        if item > best {
            best = item;
        }
    }
    best
}

fn largest_char(items: &[char]) -> char {
    let mut best = items[0];
    for &item in items {
        if item > best {
            best = item;
        }
    }
    best
}

fn main() {
    let numbers = [3, 7, 2, 9, 4];
    let letters = ['k', 'z', 'a', 'm'];
    println!("largest number: {}", largest_i32(&numbers));
    println!("largest letter: {}", largest_char(&letters));
}

It prints largest number: 9 and largest letter: z, which is correct, and that is exactly the problem. The two functions are not different in any way that matters. The loop is the same, the comparison is the same, the starting value is the same. Only the type annotation differs, and you paid for that one difference with a whole second function: a second place to fix a bug, a second place to forget to fix it.

In Go you have felt this exact pressure. Before generics arrived in the language you either copied the function per type, reached for interface and gave up compile-time type checking, or generated code with a tool. None of those is the thing you actually wanted, which was to write the logic once and have it work for every type that makes sense. That is what this chapter is about.

The fix is to give the function a type parameter: a placeholder name, conventionally T, that stands for "some type the caller will choose." You declare it in angle brackets right after the function name, fn largest<T>, and from then on you can use T in the signature and body wherever you would otherwise write a concrete type. One function now covers both lists. Run it:

// One function, written once, over any type T that can be compared and copied.
// Read <T: PartialOrd + Copy> as: "for any type T you can order and copy."
fn largest<T: PartialOrd + Copy>(items: &[T]) -> T {
    let mut best = items[0];
    for &item in items {
        if item > best {
            best = item;
        }
    }
    best
}

fn main() {
    let numbers = [3, 7, 2, 9, 4];
    let letters = ['k', 'z', 'a', 'm'];
    // The same largest serves both calls. The compiler picks T from the argument.
    println!("largest number: {}", largest(&numbers));
    println!("largest letter: {}", largest(&letters));
}

Same two answers, 9 and z, from one function this time. Look at the signature: fn largest<T: PartialOrd + Copy>(items: &[T]) -> T. The <T> introduces the placeholder. The argument is &[T], a slice of whatever T turns out to be, and the return type is a single T. You never wrote i32 or char. At each call site the compiler reads the argument, sees the element type, and decides what T is for that call: i32 for the numbers, char for the letters. You did not have to say.

The part you cannot skip is T: PartialOrd + Copy, called a trait bound: a constraint that says which types T is allowed to be. Without it the function does not compile, and the reason is worth sitting with. Inside the body you write item > best, but a bare, unconstrained T is any type at all, and not every type can be compared with >. The compiler will not let you compare two values of a type that might not support comparison. So you promise it that T can be ordered (PartialOrd) and can be copied (Copy, which is what lets best = item duplicate the value rather than move it), and now the body is allowed.

Functions are not the only thing that gets copied per type. Data structures do too. If you have a struct that pairs two values and you want one for integers and one for strings, the naive answer is two structs. The better answer is the same as before: a type parameter on the struct itself. Pair<T> below holds two values, both of the one type T the user picks. Run it:

// A generic struct: Pair<T> holds two values of one chosen type.
struct Pair<T> {
    first: T,
    second: T,
}

impl<T: Copy> Pair<T> {
    // A method that swaps the two fields, returning a fresh Pair.
    fn swapped(&self) -> Pair<T> {
        Pair { first: self.second, second: self.first }
    }
}

fn main() {
    let nums = Pair { first: 1, second: 2 };
    let words = Pair { first: "left", second: "right" };

    let flipped = nums.swapped();
    println!("nums swapped: {} {}", flipped.first, flipped.second);

    let flipped_words = words.swapped();
    println!("words swapped: {} {}", flipped_words.first, flipped_words.second);
}

The declaration is struct Pair<T>, and both fields are typed T, so the two values in a pair always share one type. Pair { first: 1, second: 2 } is a Pair<i32>, inferred from the literals; Pair { first: "left", second: "right" } is a Pair<&str>. You never spelled the type in; the compiler read it off the values you put in.

The methods need the type parameter too, and that is what the impl<T: Copy> Pair<T> line says. Read it as: "for any T that is Copy, here are the methods on Pair<T>." The <T> after impl declares the parameter for the block, and the Pair<T> after it says which type the methods attach to. The Copy bound is there for the same reason as before: swapped reads each field out by value to build a new pair, and Copy is what permits that without moving the originals out of self.

Enums take type parameters the same way structs do, and the two enums you use most are generic. Option<T> from chapter I.02 is an enum with two variants: Some(T), which carries a value of the chosen type, and None, which carries nothing. Result<T, E> is generic over two parameters. To see there is no magic in them, here is a small Slot<T> that is shaped exactly like Option, built by hand. Run it:

// A generic enum: Slot<T> is either Full with a value, or Spare with none.
// This is the exact shape of the standard library's Option<T>, built by hand.
enum Slot<T> {
    Full(T),
    Spare,
}

fn describe<T: std::fmt::Display>(slot: &Slot<T>) -> String {
    match slot {
        Slot::Full(value) => format!("holds {value}"),
        Slot::Spare => String::from("empty"),
    }
}

fn main() {
    let a: Slot<i32> = Slot::Full(42);
    let b: Slot<i32> = Slot::Spare;
    println!("{}", describe(&a));
    println!("{}", describe(&b));
}

enum Slot<T> declares the parameter, and the Full(T) variant uses it: a Slot<i32> holds an i32 in its Full arm, a Slot<String> would hold a String. The Spare variant carries no data, just like None. When you match on a Slot<T>, the value bound in the Full arm has type T, and the same destructuring you learned in III.08 works without change. The only new thing is that the payload type is a parameter rather than fixed.

Notice the bound on describe: T: std::fmt::Display. The function wants to interpolate the value into a string with {value}, and only types that can be displayed are allowed there. So describe works for any T you can print, and the compiler refuses to call it with a T that has no display, again before the program ever runs.

Most of the time you never name T at a call site, because the compiler infers it from the arguments or from the type you assign the result to. But inference needs something to go on, and sometimes nothing in the code says which type you mean. The classic case is parse: it can produce many different number types from a string, and a bare "256".parse() with no other clue leaves the compiler genuinely unable to choose. Run this:

// Usually the compiler infers T from context. Sometimes you must spell it out,
// and the turbofish ::<T> is how. "parse" can produce many number types, so
// nothing here tells it which one to make until you say so.
fn main() {
    let text = "256";

    // The turbofish names the type the parse should produce.
    let as_u8 = text.parse::<u8>();
    let as_u16 = text.parse::<u16>();

    println!("as u8:  {:?}", as_u8);  // 256 does not fit in a u8: an Err
    println!("as u16: {:?}", as_u16); // 256 fits in a u16: Ok(256)

    // The other way to steer inference is to annotate the binding instead.
    let also_u16: u16 = "1024".parse().unwrap();
    println!("annotated: {}", also_u16);
}

The syntax text.parse::<u8>() is the turbofish, named for the ::<> that looks a little like a fish swimming. It is how you supply the type parameter by hand when inference cannot. Here it tells parse exactly which number type to build, so parse::<u8>() tries for a u8 and fails because 256 overflows a byte, while parse::<u16>() succeeds. Same input, different requested type, different result.

The turbofish is not the only way to steer inference, and often not the nicest. The last line annotates the binding instead: let also_u16: u16 = "1024".parse().unwrap();. The : u16 on the variable flows backward into parse, so the compiler infers the same u16 without a turbofish in sight. Reach for the turbofish when there is no convenient binding to annotate, for example mid-expression or in a method chain; reach for a type annotation when there is.

You have already met trait bounds in passing: T: PartialOrd, T: Copy, T: Display. Each one is a promise about what T can do, and the compiler checks at the call site that the type you chose keeps the promise. The trouble is purely cosmetic: stack two or three bounds on two or three parameters and the angle brackets swell until the function name is hard to find. Rust has a tidier place to put them, the where clause. Run this:

// When the bounds get long, a where clause moves them below the signature so
// the function's shape stays readable. These two signatures mean the same thing.
use std::fmt::Display;

// Inline bounds: correct, but the angle brackets get crowded.
fn show_inline<T: Display + Clone>(value: T) -> String {
    let copy = value.clone();
    format!("{copy}")
}

// The same constraints, lifted into a where clause below the signature.
fn show<T>(value: T) -> String
where
    T: Display + Clone,
{
    let copy = value.clone();
    format!("{copy}")
}

fn main() {
    println!("{}", show_inline(7));
    println!("{}", show("hello"));
}

The two functions, show_inline and show, mean precisely the same thing; the compiler treats them as identical. In the first, the bounds sit inline: fn show_inline<T: Display + Clone>. In the second, the angle brackets hold only the bare parameter, fn show<T>, and the constraints move below the signature into a where T: Display + Clone block. With one short bound the inline form is fine. With several long ones, the where clause keeps the signature line readable and gathers every constraint in one labeled place.

The + in Display + Clone reads as "and": the type must satisfy Display and Clone, both at once. Clone is what makes value.clone() legal in the body, and Display is what makes format! able to print it. Drop either bound and the matching line stops compiling, because you would be asking T for an ability you never required of it. This is the same principle throughout the chapter: a generic can do exactly what its bounds permit, no more.

So far every type parameter has stood for a type. Rust has a second, narrower kind of generic that stands for a value known at compile time, almost always a length. It is called a const generic, written const N: usize in the angle brackets, and it lets a function be generic over the size of a fixed array. Run this:

// A const generic: the function is generic over a number N, not just a type.
// [T; N] is a fixed-size array of N items, and N is known at compile time.
fn sum<const N: usize>(values: [i64; N]) -> i64 {
    let mut total = 0;
    for v in values {
        total += v;
    }
    total
}

fn main() {
    // N is inferred from the array's length at each call: 3 here, 5 there.
    println!("sum of 3: {}", sum([10, 20, 30]));
    println!("sum of 5: {}", sum([1, 2, 3, 4, 5]));
}

The signature is fn sum<const N: usize>(values: [i64; N]). The type [i64; N] is a fixed-size array: N integers, with N baked into the type itself, so [i64; 3] and [i64; 5] are genuinely different types. Without const generics, sum would have to be written once per length, or take a slice and lose the compile-time size. With const N, the one function accepts an array of any length, and the compiler infers N from each call: 3 for the first array, 5 for the second.

The word const here is the same idea as a constant elsewhere in Rust: a value fixed at compile time, not computed at run time. That is exactly why N can be part of a type. The compiler knows the array's length while it is still compiling, so it can check your indexing and stack-allocate the array with no run-time length field at all. Const generics are how the standard library writes one impl that covers arrays of every length at once, a thing that used to require a macro spelling out each size by hand.

Here is the question a careful engineer asks about all of this. If one generic function serves many types, is there a price at run time? In some languages there is: the generic stays generic, and each operation pays a small tax to figure out, while the program runs, what concrete type it is actually holding. Rust does not work that way, and the reason has a name you met conceptually back in Part II: monomorphization. Run this:

// Monomorphization, made visible. "identity" is written once over any T, but
// the compiler stamps out a separate specialised copy for each concrete type
// you actually call it with: one for i32, one for &str. At run time there is no
// generic left, only ordinary functions, so a generic costs nothing extra.
fn identity<T>(value: T) -> T {
    value
}

fn main() {
    let n = identity(99);          // compiler emits an i32 version here
    let s = identity("unchanged"); // and a &str version here
    println!("{n}");
    println!("{s}");
}

identity is written once over T, but it is called two ways: with an i32 and with a &str. When the compiler sees those calls, it does not keep one generic function around to be sorted out later. It stamps out a separate, specialised copy of identity for each concrete type you actually use: one version whose T is i32, another whose T is &str. By the time the program runs, the generic is gone. There are only ordinary, fully concrete functions, exactly the ones you would have written by hand in section 01.

That is what "monomorphization" means, and the long word is doing honest work: mono for one, morph for shape. The many-shaped generic is turned into many one-shaped concrete functions. The payoff is the promise Part II made: a generic in Rust has zero runtime cost. The specialised copies are as fast as hand-written ones, with no type tag carried at run time and no indirection to resolve. You write the logic once and pay nothing for the abstraction.

Generics are the answer to a problem you have solved badly before: the same logic, retyped for each type it serves. You met the placeholder T on functions, then on structs and enums, and saw that the types you already use, Vec, Option, Result, are generics the library wrote once. You saw why a bare T can do nothing until a bound grants it an ability, and that bounds tidy into a where clause when they grow. You met the turbofish for the rare call where inference cannot guess, const generics for being generic over a length, and monomorphization, which makes all of it cost nothing at run time.

One thread runs ahead of this chapter on purpose, and it is the important one. Every bound in this chapter (PartialOrd, Copy, Display, Clone) was a trait, and traits are what make a generic T able to do anything at all. We requested them here just far enough to make the examples compile. The full story, what a trait is, how you define one, and how it gives a generic its powers, is the next chapter, III.10, Traits. Generics are the shape; traits are what flows through it.