Rust: Generics

4 March 2023

Let’s say we want to write a function that returns the smaller of two numbers, so we can call it like this:

let a = 4;
let b = 5;
println!("{}", min(a, b));   // prints 4

That shouldn’t be too hard. Here’s my first attempt:

fn min(x: i32, y: i32) -> i32 {
    if x < y { x } else { y }
}

This works for the example above, but it’ll only work with i32 numbers. What if we want to use it with i64 numbers? We could copy the code, replace i32 with i64 everywhere, and rename the function, but then we’ll have to do that for every type we want to use. Ideally, we’d just replace i32 with a placeholder, something like this:

// T can be i32, i64, or any other type that we can compare with <
fn min(x: T, y: T) -> T {
    if x < y { x } else { y }
}

It turns out we can do pretty much that! Here’s what it looks like with proper Rust syntax:

fn min<T>(x: T, y: T) -> T
where T: PartialOrd {
    if x < y { x } else { y }
}

The <T> after the function name tells the compiler that this function has a type parameter called T. In the function definition, we can then use T as if it was a real type. The where clause in the next line puts a limitation on what T can be: T has to be a type that implements the PartialOrd trait, which means we can use the < operator on x and y. This is called a trait bound.

When calling min we can set T explicitly:

println!("{}", min::<i32>(4, 5));   // T is i32

…but in many cases we can rely on the compiler to infer the type:

println!("{}", min(4, 5));          // T is inferred to be i32
println!("{}", min(4.0, 5.0));      // T is inferred to be f64
println!("{}", min(true, false));   // T is inferred to be bool

(If you’re wondering, that last one prints false.)

During compilation, the compiler will generate multiple versions of this function, one for each type that’s needed in your program. For the sample code, it would generate three functions more-or-less like this:

fn min_i32(x: i32, y: i32) -> i32 {
    if x < y { x } else { y }
}

fn min_i64(x: i64, y: i64) -> i64 {
    if x < y { x } else { y }
}

fn min_bool(x: bool, y: bool) -> bool {
    if x < y { x } else { y }
}

In Rust, min is called a generic function, and the programming language feature is called generics.

The more computer-sciencey term is parametric polymorphism, which is a bit of a mouthful, but I would argue it’s actually a better name: “polymorphic” means “able to have several shapes or forms”, so parametric polymorphism means something can have several forms depending on a parameter. That’s exactly what’s happening with the min function and the T parameter. By comparison, the name “generics” is a bit, well, generic. The Rust documentation always calls it generics, though, so that’s also what I’ll use here.

One more thing about the syntax. In simple cases like this we can leave out the where clause and put the trait bound in the angle brackets:

fn min<T: PartialOrd>(x: T, y: T) -> T {
    if x < y { x } else { y }
}

Generic types

The most common use of generics are not generic functions but generic types. The standard library has quite a few, including Option<T> and Result<T, E>. Defining your own isn’t too complicated, either. Let’s say we want to represent “nullable” types like the ones in SQL. Instead of defining types NullableBool, NullableInteger, and so on, we can define a generic Nullable type:

#[derive(Debug)]
enum Nullable<T> {
    Null,
    Value(T),
}

We can create a Nullable<bool> like this:

let a = Nullable::Value(true);

Here, the compiler can infer type T from the argument. For Null values there is no argument, so we have to set the type with a type annotation or the turbofish operator:

let b: Nullable<bool> = Nullable::Null;
let c = Nullable::<bool>::Null;

To define methods on a generic type, we add a parameter to the impl keyword:

impl<T> Nullable<T> {
    fn is_null(&self) -> bool {
        match self {
            Nullable::Null => true,
            _ => false,
        }
    }
}

Now is_null is available for any Nullable<T> type that we’d like to use it with! We can also define a method on a concrete type like Nullable<bool>, though. For example, the not operator in SQL only works for booleans, so we can implement it like this:

impl Nullable<bool> {
    fn not(&self) -> Nullable<bool> {
        match self {
            &Nullable::Value(a) => Nullable::Value(!a),
            _ => Nullable::Null,
        }
    }
}

We can call those methods like any other:

println!("{:?}", a.is_null());   // prints false
println!("{:?}", b.is_null());   // prints true
println!("{:?}", a.not());       // prints Value(false)

Const parameters

In addition to type parameters, we can use const parameters to write code parameterized with an integer or boolean. As an example, let’s say we want a type for numbers with a limited range. We can define a struct that’s parameterized with two integers for minimum and maximum:

#[derive(Debug)]
struct Number<const MIN: i64, const MAX: i64> {
    value: i64,
}

The syntax for parameters is like that for regular constants in Rust. To define methods (or associated functions) for this type we’ll need an impl block that’s parameterized in the same way:

impl<const MIN: i64, const MAX: i64> Number<MIN, MAX> {
    fn new(value: i64) -> Option<Number<MIN, MAX>> {
        if value < MIN || value > MAX {
            None
        } else {
            Some(Number { value })
        }
    }
}

Const generics are a relatively recent addition to the language; they were added in Rust 1.51, released in March 2021.

Generic traits

Traits can also be generic. Here’s a trait for a table (or dictionary, or map) with type parameters for keys and values:

trait Table<K: PartialEq, V> {
    fn insert(&mut self, key: K, value: V);
    fn lookup(&self, key: K) -> Option<V>;
}

We can write a simple implementation of the trait that just stores keys-value pairs in a vector. Here’s the type:

struct SimpleTable<K, V> {
    list: Vec<(K, V)>,
}

Before we implement the trait, let’s add a new method so we can easily construct an empty SimpleTable:

impl<K, V> SimpleTable<K, V> {
    fn new() -> SimpleTable<K, V> {
        SimpleTable { list: vec![] }
    }
}

Finally, we have the trait implementation. Because Table and SimpleTable are both generic, we need three sets of type parameters, for the impl keyword, the type, and the trait:

impl<K: PartialEq, V: Copy> Table<K, V> for SimpleTable<K, V> {
    fn insert(&mut self, key: K, value: V) {
        if let Some((_, ref mut v)) = self.list.iter_mut().find(|(k, _)| *k == key) {
            *v = value
        } else {
            self.list.push((key, value))
        }
    }
    
    fn lookup(&self, key: K) -> Option<V> {
        self.list.iter().find(|(k, _)| *k == key).map(|(_, v)| *v)
    }
}

Anonymous type parameters

To conclude this article I want to go back to something I mentioned at the end of my article on traits: using the impl keyword for function parameters. Let’s define a very simple function that takes a reference to a Table:

fn has_zero(table: &dyn Table<i64, i64>) -> bool {
    table.lookup(0).is_some()
}

We can call it with a SimpleTable object:

let mut table: SimpleTable<i64, i64> = SimpleTable::new();
println!("has zero? {}", has_zero(&table));

At runtime, this will build a trait object and pass it to has_zero, which uses the vtable and the object pointer so it can call lookup. That works fine, but it’s a lot of overhead for such a simple function. A generic function would be more efficient:

fn has_zero<T: Table<i64, i64>>(table: &T) -> bool {
    table.lookup(0).is_some()
}

The impl syntax is just another way to write this generic function:

fn has_zero(table: &impl Table<i64, i64>) -> bool {
    table.lookup(0).is_some()
}

The Rust Reference calls this anonymous type parameters: this last version of has_zero is parameterized with a type, but that type doesn’t actually have a name. The code just says it must be a type that implements Table<i64, i64>.