Generics: Avoiding Code Duplication for Different Types

About This Module

This module introduces Rust's powerful generics system, which allows writing flexible, reusable code that works with multiple types while maintaining type safety and performance. You'll learn how to create generic functions, structs, and methods, as well as understand key built-in generic types like Option<T> and Result<T, E>.

Prework

Prework Reading

Please read the following sections from The Rust Programming Language Book:

Chapter 10.1: Generic Data Types
Chapter 10.2: Traits (for understanding trait bounds)
Chapter 6.1: Defining an Enum (for Option review)
Chapter 9.2: Recoverable Errors with Result (for Result<T, E> review)

Pre-lecture Reflections

How do generics in Rust compare to similar features in languages you know (templates in C++, generics in Java)?
What are the performance implications of Rust's monomorphization approach?
Why might Option<T> be safer than null values in other languages?
When would you choose Result<T, E> over Option<T>?

Learning Objectives

By the end of this module, you will be able to:

Write generic functions and structs using type parameters
Apply trait bounds to constrain generic types
Use Option<T> and Result<T, E> for safe error handling
Understand monomorphization and its performance benefits

How python handles argument types

Python is dynamically typed and quite flexible in this regard. We can pass many different types to a function.

def max(x,y):
    return x if x > y else y

>>> max(3,2)
3

>>> max(3.1,2.2)

3.1

>>> max('s', 't')
't'

Very flexible! Any downsides?

Requires inferring types each time function is called
Incurs runtime penalty
No compile-time guarantees about type safety

>>> max('s',5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in max
TypeError: '>' not supported between instances of 'str' and 'int'

Rust without generics

Rust is strongly typed, so we would have to create a version of the function for each type.

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

fn max_f64(x:f64,y:f64) -> f64 {
    if x > y {x} else {y}
}

fn max_char(x:char,y:char) -> char {
    if x > y {x} else {y}
}

fn main() {
    println!("{}", max_i32(3,8));
    println!("{}", max_f64(3.3,8.1));
    println!("{}", max_char('a','b'));
}

Rust Generics

Generics allow us to write one version of a function and then have the compiler generate versions for different types.

The process of going from one to the other is monomorphization.

  GENERIC SOURCE                 COMPILER OUTPUT (roughly)
┌─────────────────┐            ┌─────────────────────┐
│ fn pass<T>(x:T) │  ────────► │ fn pass_i32(x:i32)  │
│ { ... }         │            │ fn pass_f64(x:f64)  │
│                 │            │ fn pass_char(x:char)│
└─────────────────┘            └─────────────────────┘
     One source                 Multiple functions

Rust Generics: Syntax

Use the <T> syntax to indicate that the function is generic.

The T is a placeholder for the type and could be any character.

fn passit<T>(x:T) -> T {
    x
}

fn main() {
let x = passit(5);
println!("x is {x}");

let x = passit(1.1);
println!("x is {x}");

let x = passit('s');
println!("x is {x}");
}

Watch Out!

Let's try this:

// ERROR -- this doesn't work
fn show<T>(x:T,y:T){
    println!("x is {x} and y is {y}");
}

fn main() {
    show(3,5);
    show(1.1, 2.1);
    show('s', 't');
}

The Rust compiler is thorough enough to recognize that not all generic type may have the behavior we want.

The Fix: Trait Bounds

We can place restrictions on the generic types we would support.

fn show<T: std::fmt::Display>(x:T,y:T){
    println!("x is {x} and y is {y}");
}

fn main() {
    show(3,5);
    show(1.1, 2.1);
    show('s', 't');
    show( "hello", "world");
    show( true, false);
    //show( vec![1,2,3], vec![4,5,6]); // doesn't work
}

We'll talk about traits in the next module.

Another Watch Out!

// ERROR -- similarly we could try this, but it doesn't work
fn max<T>(x:T,y:T) -> T {
        if x > y {x} else {y}
}

fn main() {
    println!("{}", max(3,8));
    println!("{}", max(3.3,8.1));
    println!("{}", max('a','b'));
}

Not all types support the > operator.

The Fix: Trait Bounds

We can further restrict the type of T to only allow types that implement the PartialOrd trait.

// add info that elements of T are comparable
fn max<T:PartialOrd>(x:T,y:T) -> T {
        if x > y {x} else {y}
}

fn main() {
    println!("{}",max(3,8));
    println!("{}",max(3.3,8.1));
    println!("{}",max('a','b'));
}

Generics / Generic data types

In other programming languages:

C++: templates
Java: generics
Go: generics
ML, Haskell: parametric polymorphism

Generic Structs

We can define a struct that is generic.

#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

fn main() {
let point_int = Point {x: 2, y: 3};
println!("{:?}", point_int);

let point_float = Point {x: 4.2, y: 3.0};
println!("{:?}", point_float);
}

Struct contructor method

We can define methods in the context of Structs that support generic data types

impl<T> Point<T> means that this is an implementation block and all the methods are implemented for any type T that Point might be instantiated with.

#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

// define a constructor method for the Point struct
impl<T> Point<T> {
    fn create(x:T,y:T) -> Point<T> {
        Point{x,y}
    }
}

fn main() {
    // create instances of the Point struct using the constructor method
    let point = Point::create(1, 2);
    let point2 = Point::<char>::create('c','d');
    let point3 : Point<char> = Point::create('e','f');
    println!("{:?} {:?} {:?}", point, point2, point3);
}

Struct swap method

Let's implement another method that operates on an instance of the struct, hence the use of &mut self.

Remember, &mut self means that the method is allowed to modify the instance of the struct.

#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

// define a constructor method for the Point struct
impl<T> Point<T> {
    fn create(x:T,y:T) -> Point<T> {
        Point{x,y}
    }
}

// implement a method that swaps the x and y values
impl<T:Copy> Point<T> {
    fn swap(&mut self) {
        let z = self.x;
        self.x = self.y;
        self.y = z;
    }
}

fn main() {
    let mut point = Point::create(2,3);
    println!("{:?}",point);
    point.swap();
    println!("{:?}",point);
}

impl<T:Copy> specifies that T must implement the Copy trait.

You can see what happens if we remove the Copy trait.

Question: What datatype might not implement the Copy trait?

Specialized versions

Even though we have generic functions defined, we can still specify methods/functions for specific types.

#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

// define a constructor method for the Point struct
impl<T> Point<T> {
    fn create(x:T,y:T) -> Point<T> {
        Point{x,y}
    }
}

impl Point<i32> {
    fn do_you_use_f64(&self) -> bool {
        false
    }
}

impl Point<f64> {
    fn do_you_use_f64(&self) -> bool {
        true
    }
}

fn main() {
    let p_i32 = Point::create(2,3);
    println!("p_i32 uses f64? {}",p_i32.do_you_use_f64());

    let p_f64 = Point::create(2.1,3.1);
    println!("p_f64 uses f64? {}",p_f64.do_you_use_f64());
}

Useful predefined generic data types

There are two useful predefined generic data types: Option<T> and Result<T, E>.

Enum `Option<T>`

There is a built-in enum Option<T> in the standard library with two variants:

Some(T) -- The variant Some contains a value of type T
None

Useful for when there may be no output

Compared to None or null in other programming languages:
- Rust forces handling of this case

From Option enum advantage over null:

The Option type encodes the very common scenario in which a value could be something or it could be nothing.

For example, if you request the first item in a non-empty list, you would get a value. If you request the first item in an empty list, you would get nothing.

Expressing this concept in terms of the type system means the compiler can check whether you’ve handled all the cases you should be handling;

This functionality can prevent bugs that are extremely common in other programming languages.

Null

Example: Prime Number Finding

Here's example prime number finding code that returns Option<u32> if a prime number is found, or None if not.

fn prime(x:u32) -> bool {
    if x <= 1 { return false;}

    // factors would come in pairs. if one factor is > sqrt(x), then
    // the other factor must be < sqrt(x).
    // So we only have to search up to sqrt(x)
    for i in 2..=((x as f64).sqrt() as u32) {
        if x % i == 0 { // can be divided by i without a remainder -> not prime
            return false;
        }
    } 
    true
}

fn prime_in_range(a:u32,b:u32) -> Option<u32> {  // returns an Option<u32>
    for i in a..=b {
        if prime(i) {return Some(i);}
    }
    None
}

fn main() {
    println!("prime in 90-906? {:?}",prime_in_range(90,906));

    println!("prime in 90-92? {:?}",prime_in_range(90,92));

    let tmp : Option<u32> = prime_in_range(830,856);
    println!("prime in 830-856? {:?}",tmp);
}

If a prime number is found, it returns Some(u32) variant with the prime number.
If the prime number is not found, it returns None.

Extracting the content of `Some(...)`

There are various ways to extract the content of Some(...)

if let
match
unwrap()

fn prime(x:u32) -> bool {
    if x <= 1 { return false;}

    // factors would come in pairs. if one factor is > sqrt(x), then
    // the other factor must be < sqrt(x).
    // So we only have to search up to sqrt(x)
    for i in 2..=((x as f64).sqrt() as u32) {
        if x % i == 0 { // can be divided by i without a remainder -> not prime
            return false;
        }
    } 
    true
}

fn prime_in_range(a:u32,b:u32) -> Option<u32> {  // returns an Option<u32>
    for i in a..=b {
        if prime(i) {return Some(i);}
    }
    None
}

fn main() {
    let tmp : Option<u32> = prime_in_range(830,856);

    // extracting the content of Some(...)
    if let Some(x) = tmp {
        println!("{}",x);
    }

    match tmp {
        Some(x) => println!("{}",x),
        None => println!("None"),
    };

    println!("Another way {}", tmp.unwrap())
}

Be careful with `unwrap()`

Be careful with unwrap(), it will crash the program if the value is None.

//ERROR
fn main() {
    // extracting the content of Some(...)
    let tmp: Option<u32> = None;  // try changing this to Some(3)

    if let Some(x) = tmp {
        println!("{}",x);   // will skip this block if tmp is None
    }
    match tmp {
        Some(x) => println!("{}",x),
        None => println!("{:?}", tmp),
    };

    // Boom!!!!! Will crash the program if tmp is None
    println!("Another way {}", tmp.unwrap())
}

There is always a prime number in $[k, 2 k]$ . See Prime Number Theorem

Enum `Option<T>`: useful methods

Check the variant

.is_some() -> bool
.is_none() -> bool

Get the value in Some or terminate with an error

.unwrap() -> T
.expect(message) -> T

Get the value in Some or a default value

.unwrap_or(default_value:T) -> T

#![allow(unused)]
fn main() {
let x = Some(3);
println!("x is some? {}",x.is_some());
}

If exception, print a message.

#![allow(unused)]
fn main() {
// Try line 3 instead of 4

//let x:Option<u32> = Some(3);
let x = None;
let y:u32 = x.expect("This should have been an integer!!!");
println!("y is {}",y);
}

A better way to handle this is to use unwrap_or().

#![allow(unused)]
fn main() {
let x = None;
println!("{}",x.unwrap_or(0));

let y = Some(3);
println!("{}",y.unwrap_or(0));

}

More details:

https://doc.rust-lang.org/std/option/
https://doc.rust-lang.org/std/option/enum.Option.html

Enum `Result<T, E>`

Another built-in enum Result<T, E> in the standard library with two variants:

Ok(T)
Err(E)

Useful when you want to pass a solution or information about an error.

fn divide(a:u32,b:u32) -> Result<u32,String> {
    match b {
        0 => Err(String::from("Division by zero")),
        _ => Ok(a / b)
    }
}

fn main() {
    println!("{:?}",divide(3,0));
    println!("{:?}",divide(2022,3));
}

Enum `Result<T, E>`: useful methods

Check the variant

.is_ok() -> bool
.is_err() -> bool

Get the value in Ok or terminate with an error

.unwrap() -> T
.expect(message) -> T

Get the value in Ok or a default value

.unwrap_or(default_value:T) -> T

#![allow(unused)]
fn main() {
let r1 : Result<i32,()> = Ok(3);
println!("{}",r1.is_err());
println!("{}",r1.is_ok());
println!("{}",r1.unwrap());
}

But again, that will crash the program if the value is Err, so use unwrap_or().

#![allow(unused)]
fn main() {
let r2 : Result<u32,()> = Err(());
let r3 : Result<u32,()> = Ok(123);
println!("r2: {}\nr3: {}",
    r2.unwrap_or(0),
    r3.unwrap_or(0));

}

More details:

https://doc.rust-lang.org/std/result/
https://doc.rust-lang.org/std/result/enum.Result.html

In-Class Poll

Will be opened and made visible in class.

In-Class Activity: Practicing Generics

Time: 10 minutes

Instructions

Work individually or in pairs. Complete as many exercises as you can in 10 minutes. You can test your code in the Rust playground or in your local environment.

Exercise 1: Fix the Generic Function (3 minutes)

The following code doesn't compile. Fix it by adding the appropriate trait bound(s).

// TODO: Fix this function so it compiles
fn compare_and_print<T>(a: T, b: T) {
    if a > b {
        println!("{} is greater than {}", a, b);
    } else {
        println!("{} is less than or equal to {}", a, b);
    }
}

fn main() {
    compare_and_print(10, 5);
    compare_and_print(2.71, 3.14);
    compare_and_print('z', 'a');
}

Hint

You need TWO trait bounds:

One to enable comparison (>)
One to enable printing with {}

Exercise 2: Complete the Generic Struct (4 minutes)

Complete the Container<T> struct by implementing the missing methods.

#[derive(Debug)]
struct Container<T> {
    value: T,
}

impl<T> Container<T> {
    // TODO: Implement a constructor that creates a new Container
    fn new(value: T) -> Container<T> {
        // Your code here
    }
    
    // TODO: Implement a method that returns a reference to the value
    fn get(&self) -> &T {
        // Your code here
    }
    
    // TODO: Implement a method that replaces the value and returns the old one
    fn replace(&mut self, new_value: T) -> T {
        // Your code here
    }
}

fn main() {
    let mut container = Container::new(42);
    println!("Value: {:?}", container.get());
    
    let old_value = container.replace(100);
    println!("Old value: {}, New value: {:?}", old_value, container.get());
}

Hint for replace()

Use std::mem::replace(&mut self.value, new_value) or swap manually using a temporary variable.

Exercise 3: Use Option (3 minutes)

Implement a function that finds the first even number in a vector. Return Some(number) if found, or None if no even numbers exist.

// TODO: Implement this function
fn find_first_even(numbers: &Vec<i32>) -> Option<i32> {
    // Your code here
}

fn main() {
    let numbers1 = vec![1, 3, 5, 7];
    let numbers2 = vec![1, 3, 6, 7];
    
    match find_first_even(&numbers1) {
        Some(n) => println!("Found even number: {}", n),
        None => println!("No even numbers found"),
    }
    
    // TODO: Use unwrap_or() to print the result with a default value of -1
    println!("First even in numbers2: {}", /* your code here */);
}

Bonus Challenge (if you finish early)

Combine everything you learned! Create a generic Pair<T, U> struct that can hold two values of different types, and implement a method swap() that returns a new Pair<U, T> with the values swapped.

// TODO: Define the struct and implement the method
struct Pair<T, U> {
    // Your code here
}

impl<T, U> Pair<T, U> {
    fn new(first: T, second: U) -> Self {
        // Your code here
    }
    
    fn swap(self) -> Pair<U, T> {
        // Your code here
    }
}

fn main() {
    let pair = Pair::new(42, "hello");
    let swapped = pair.swap();
    // This should compile and show that types are swapped!
}

Solutions

Click to reveal solutions (try on your own first!)

Exercise 1 Solution

fn compare_and_print<T: PartialOrd + std::fmt::Display>(a: T, b: T) {
    if a > b {
        println!("{} is greater than {}", a, b);
    } else {
        println!("{} is less than or equal to {}", a, b);
    }
}

fn main() {
    compare_and_print(10, 5);
    compare_and_print(2.71, 3.14);
    compare_and_print('z', 'a');
}

Exercise 2 Solution

#[derive(Debug)]
struct Container<T> {
    value: T,
}

impl<T> Container<T> {
    fn new(value: T) -> Container<T> {
        Container { value }
    }
    
    fn get(&self) -> &T {
        &self.value
    }
    
    fn replace(&mut self, new_value: T) -> T {
        std::mem::replace(&mut self.value, new_value)
    }
}

fn main() {
    let mut container = Container::new(42);
    println!("Value: {:?}", container.get());
    
    let old_value = container.replace(100);
    println!("Old value: {}, New value: {:?}", old_value, container.get());
}

Exercise 3 Solution

fn find_first_even(numbers: &Vec<i32>) -> Option<i32> {
    for &num in numbers {
        if num % 2 == 0 {
            return Some(num);
        }
    }
    None
}

fn main() {
    let numbers1 = vec![1, 3, 5, 7];
    let numbers2 = vec![1, 3, 6, 7];
    
    match find_first_even(&numbers1) {
        Some(n) => println!("Found even number: {}", n),
        None => println!("No even numbers found"),
    }
    
    println!("First even in numbers2: {}", find_first_even(&numbers2).unwrap_or(-1));
}

Bonus Solution

#[derive(Debug)]
struct Pair<T, U> {
    first: T,
    second: U,
}

impl<T, U> Pair<T, U> {
    fn new(first: T, second: U) -> Self {
        Pair { first, second }
    }
    
    fn swap(self) -> Pair<U, T> {
        Pair {
            first: self.second,
            second: self.first,
        }
    }
}

fn main() {
    let pair = Pair::new(42, "hello");
    let swapped = pair.swap();
    // This should compile and show that types are swapped!
}

DS210 Course Notes