Algebraic data types

Rust types cheat sheet

Type Value range # values
bool true, false 2
u8 0, 1, …, 255 256
i8 -127, -126, …, -1, 0, 1, …, 128 256

How many different Students?

struct Student {
    is_hungry: bool,    // 2
    is_motivated: bool, // 2
}

// Example:
let me_before_lunch = Student {
    is_hungry: true,
    is_motivated: false,
};

4

How many different Professors?

struct Professor {
    is_hungry: bool,  // 2
    publications: u8, // 256
}

// Example:
let me_in_ten_years = Professor {
    is_hungry: true,
    publications: 156,
};

512

How many different Outfits?

struct Outfit {
    shoe: u8,   // 256
    tie: u8,    // 256
    jacket: u8, // 256
}

// Example:
let me_in_first_lecture = Outfit {
    shoe: 17,  // Blue sneakers to feel hip and young
    tie: 84,   // That one my girlfriend gave me last year
    jacket: 2, // The one that makes me look sexy
};

\(2^{24}=16777216\)

Is there a rule for the number of values?

struct Student {
    is_hungry: bool,   
    is_motivated: bool,
}
struct Professor {
    is_hungry: bool, 
    publications: u8,
}
struct Outfit {
    shoe: u8,  
    tie: u8,   
    jacket: u8,
}

\[ |A \times B| = |A| \times |B| \]

\[ |A \times B \times \dots \times N| = \prod_{i \in \{A,B,...,N\}}^{} |i| \]

Write a struct for a traffic light with exactly three states: Red, yellow, green

Discuss with your neighbor for 2 minutes!

Type Value range # values
bool true, false 2
u8 0, 1, …, 255 256
i8 -127, -126, …, -1, 0, 1, …, 128 256

It doesn’t work :(

Enter enum

enum TrafficLight {
    Red,    // 1
    Yellow, // 1
    Green,  // 1
}

// Usage:
let red = TrafficLight::Red;
let green = TrafficLight::Green;

enum with data

enum TrafficLight {
    Red,                // 1
    Yellow {            // 2
        with_red: bool,
    },
    Green,              // 1
}

// Usage:
let coming_yellow = TrafficLight::Yellow {
    with_red: false,
};
let going_yellow = TrafficLight::Yellow {
    with_red: true,
};

\[ |A + B| = |A| + |B| \]

struct or enum?

  • The planets of our solar system
  • Books with title, author, publication date
  • Shapes in a 2D drawing app (line, circle, rectangle)
  • Operations in a calculator (add, subtract, multiply etc.)

null in Rust

  • Rust enums are perfect to model the absence of a value:
// Of a specific type:
enum MaybeNumber {
  Number(i32),
  Nothing,
}

// For all types:
enum Option<T> {
  Some(T),
  None,
}
  • An idea from functional programming (the Maybe monad)

Why Option<T> is cool

  • enum is only part of the equation, the other half is called pattern matching:
fn add_one(number: Option<i32>) -> Option<i32> {
  match number {
    Some(num) => Some(num + 1)
    None => None, // Impossible to access a "null" value!
  }
}

fn main() {
  let some_num = Some(42);
  let no_num = None;

  println!("{:?}", add_one(some_num));
  println!("{:?}", add_one(no_num));
}

Examples of Option<T>

  • Allow us to turn partial functions into total functions
fn div(a: i32, b: i32) -> Option<i32> {
  if b == 0 {
    None
  } else {
    Some(a / b)
  }
}

fn log2(num: f32) -> Option<f32> {
  if num <= 0.0 {
    None
  } else {
    Some(num.log2())
  }
}

enum on the hardware level

  • The smallest unit of memory that Rust allows is a byte (with 256 states)
  • The size of every type is a whole number of bytes (no types taking half a byte!)
  • What is the size and memory layout of the following enum?
enum TrafficLight {
    Red,    // 1
    Yellow, // 1
    Green,  // 1
}

enum on the hardware level (cont.)

  • enum in Rust is a discriminated union (also called tagged union)
  • Its memory layout may look like this:

N=sizeof(tag)

M=sizeof(biggest variant)

Is Option<T> zero-overhead?

  • We want the same runtime performance:
    • Same number of operations
    • Same memory usage
  • Let’s check with std::mem::size_of:
Type Size (bytes) Size of T + bool
Option<i32> 8 5
Option<NonZeroI32> 4 5
Option<bool> 1 2
Option<&i32> 8 9

The null pointer optimization

  • Some types have a niche: A value that is technically representible but that they will never hold in practice
  • For Option<T>, the compiler can use this niche as the discriminant:
    • 0 for Option<NonZeroI32>
    • null for Option<&T>
  • Doesn’t work for user-defined types unfortunately…

Option<T> usage

fn add_one(number: Option<u8>) -> Option<u8> {
    match number {
        Some(num) => Some(num + 1),
        None => None,
    }
}

fn add_one_verbose(number: Option<u8>) -> Option<u8> {
    if number.is_none() {
        None
    } else {
        let num = number.unwrap(); // Won't panic 
        Some(num + 1)
    }
}

Patterns on Option<T>

  • “Take value if it exists and do something to it” is a common pattern and has its own function: map

let one = Some(1);
let two = one.map(|n| n + 1);
                //---------
                // anonymous 
                // function

Higher order functions

  • Option::map is a higher order function: A function taking a function:
pub fn map<U, F>(self, f: F) -> Option<U>
    where F: FnOnce(T) -> U,
  • Uses generics to encode “any function from T to U”
  • Everything happens by-value:
    • The Option<T> is consumed (first argument of type self)
    • The function takes ownership of the type T
    • It returns a new type U by value

Option<T> cheat sheet