# Generics

## Generic functions

In mathematics, we often express abstract concepts, e.g.,

`swap(x, y)`: swaps the values `x` and `y`.

However, in Rust, since a program must declare the types of its parameters, it would have to define a separate `swap()` function for each type of `x` and `y`, e.g.,

``````
# #![allow(unused_variables)]
#fn main() {
fn swap_i32(x: i32, y: i32) -> (i32, i32) {
(y, x)
}

fn swap_f64(x: f64, y: f64) -> (f64, f64) {
(y, x)
}

let (a, b) = (1, 2);
let (x, y) = swap_i32(a, b);
assert_eq!(x, 2);
assert_eq!(y, 1);

let (a, b) = (1.0, 2.0);
let (x, y) = swap_f64(a, b);
assert_eq!(x, 2.0);
assert_eq!(y, 1.0);
#}``````

While this solution works, it is unsatisfactory because it is repetitive. `swap_i32()` and `swap_f64()` are identical except for the parameter types. To overcome this limitation, Rust allows a program to use generic types, where instead of a concrete type such as `i32` or `f64`, a generic type `T` can represent any concrete type. It works as follows:

1. Declare a type parameter in `<>` right after the function name.
2. Use the type parameter in the types of parameters, return value, or variables in the function body.
``````fn swap<T>(x: T, y: T) -> (T, T) {
(y, x)
}

let (a, b) = (1, 2);
let (x, y) = swap(a, b);
assert_eq!(x, 2);
assert_eq!(y, 1);

let (a, b) = (1.0, 2.0);
let (x, y) = swap(a, b);
assert_eq!(x, 2.0);
assert_eq!(y, 1.0);
``````

When the program above calls `swap()`, Rust infers the concrete type for the type parameter `T` based on the types of function parameters. For example, when the program calls `swap(x, y)` and both `x` and `y` are `i32`, then Rust infers that `T` is `i32`. If, however, the types of `x` and `y` are different, the type inference fails, so Rust issues an error.

``````
# #![allow(unused_variables)]
#fn main() {
fn swap<T>(x: T, y: T) -> (T, T) {
(y, x)
}

let (a, b) = (1, 2.0);
// Error: cannot infer the concrete type of type parameter `T`
let (x, y) = swap(a, b);
#}``````

Occasionally, the compiler cannot infer the concrete type of `T` reliably. In this case, the program can explicitly state the concrete type by type hint:

``````
# #![allow(unused_variables)]
#fn main() {
fn swap<T>(x: T, y: T) -> (T, T) {
(y, x)
}

let (a, b) = (1, 2);
// `::<i32>` is a *type hint* stating the concrete type of the type parameter `T`
let (x, y) = swap::<i32>(a, b);
#}``````

## Generic structs and enums

We saw the use of the enum type `Option` to represent both a valid value `Some()` and an error `None`. To allow `Option` to represent values of any types, we declare a type parameter `T` and use it as the type of the value in `Some()`.

``````
# #![allow(unused_variables)]
#fn main() {
enum Option<T> {
Some(T),
None,
}

// Type inference: T is i32
let x = Option::Some(1);
// Type hint
let x = Option::Some::<i32>(1);
// Type inference: T is f64
let x = Option::Some(1.0);
// Type hint
let x = Option::Some::<f64>(1.0);
#}``````

If we wish to distinguish between different types of errors, we could use `Result<T, E>`, which takes two type parameters.

``````
# #![allow(unused_variables)]
#fn main() {
enum Result<T, E> {
Ok(T),
Err(E),
}

struct MemoryError {}

struct IoError {}

// Type inference: `T` is `i32` and `E` is `MemoryError`
let mut x = Result::Ok(1);
x = Result::Err(MemoryError{});

// Type hint
let y = Result::Ok::<f64, IoError>(1.0);
let z = Result::Err::<f64, IoError>(IoError{});
#}``````

Note that in the following program, Rust cannot infer the concrete types of all the type parameters, so the program must provide adequate type hints or explicitly declare the types of the variables.

``````
# #![allow(unused_variables)]
#fn main() {
enum Result<T, E> {
Ok(T),
Err(E),
}

struct MemoryError {}

struct IoError {}

// Must provide the concrete type of `E`
let x = Result::Ok::<_, MemoryError>(1);
// Alternatively, declare its type.
let x: Result<_, MemoryError> = Result::Ok(1);
// Must provide the concrete type of `T`
let y = Result::Err::<i32, _>(IoError{});
// Alternatively, declare its type.
let y: Result<i32, _> = Result::Err(IoError{});
#}``````

You may also define generic structs.

``````struct Polygon<T> {
center: (T, T),
sides: i32,
}

impl<T> Polygon<T> {
fn get_sides(&self) -> i32 {
self.sides
}
}

let x = Polygon{ center: (0.0, 1.0), radius: 1.0, sides: 5 };
assert_eq!(x.get_sides(), 5);
``````

## Monomorphization

Generics are called parametric polymorphism, because they provide multiple forms (polymorphism) via type parameters. Consistent with Rust's philosophy of zero-cost abstraction, generics incur no runtime cost thanks to monomorphization, or "converting to single forms".

For each generic item (function, enum, or struct), and for each unique assignment of concrete types to the item's type parameters, Rust creates a separate copy of the item where it replaces all the type parameters with their corresponding concrete types.

For example, the following generic program

``````
# #![allow(unused_variables)]
#fn main() {
fn swap<T>(x: T, y: T) -> (T, T) {
(y, x)
}

let (a, b) = (1, 2);
let (x, y) = swap(a, b);

let (a, b) = (1.0, 2.0);
let (x, y) = swap(a, b);
#}``````

after monomorphization, becomes

``````
# #![allow(unused_variables)]
#fn main() {
fn swap_i32(x: i32, y: i32) -> (i32, i32) {
(y, x)
}

fn swap_f64(x: f64, y: f64) -> (f64, f64) {
(y, x)
}

let (a, b) = (1, 2);
let (x, y) = swap_i32(a, b);

let (a, b) = (1.0, 2.0);
let (x, y) = swap_f64(a, b);
#}``````

In other words, the compiler converts the generic program to the original one without generics that we wrote by hand! Generics allow the programmer to focus on the algorithms while abstracting away concrete data types, leaving the boring monomorphization to the compiler. This is similar to how C++ handles generics (called templates in C++), but different than how Java handles generics (via type erasure).