Enums and the Algebraic Sum

You have hit this problem in every language you have used. A value is one of a small, fixed set of things: an order is pending or shipped or delivered; a traffic light is red, yellow, or green; a JSON node is a number, a string, an array, or an object. In Go you usually reach for a handful of const integers and a type Status int, or a string you agree to spell the same way everywhere. Nothing stops you assigning Status(99), though, or typing "shippd" by mistake. The set of allowed values lives in your head and your discipline, not in the type.

Rust’s answer is the enum: a type whose definition lists by name every shape a value of that type may take. Read this one, then press Run:

// An enum lists, by name, every shape a value is allowed to take.
// A light is exactly one of these three at a time, never two, never none.
enum Light {
    Red,
    Yellow,
    Green,
}

fn next(light: Light) -> Light {
    match light {
        Light::Red => Light::Green,
        Light::Green => Light::Yellow,
        Light::Yellow => Light::Red,
    }
}

fn name(light: &Light) -> &'static str {
    match light {
        Light::Red => "red",
        Light::Yellow => "yellow",
        Light::Green => "green",
    }
}

fn main() {
    let mut light = Light::Red;
    for _ in 0..4 {
        println!("light is {}", name(&light));
        light = next(light);
    }
}

Light has exactly three possible values: Light::Red, Light::Yellow, and Light::Green. These are called the enum’s variants: the named alternatives a value is allowed to be. A Light is always one of them, never a fourth thing, never two at once, and never absent. There is no Light::Blue to typo into existence, because every legal value is written down in the type. The match from I.01 does the case analysis: one arm per variant, and the compiler checks you covered them all.

This is the same word Go and C use, enum, but it is a stronger thing. In C an enum is a thin coat of paint over integers, and any int can be cast into it. In Rust a Light is its own type with its own set of values, and the only way to make one is to name a variant. Pinned to stable Rust 1.96.0, that guarantee holds: you cannot smuggle a stray number in where a Light is expected.

A plain list of labels is useful, but enums in Rust go further than Go’s integer constants in one decisive way: each variant can carry its own data, and different variants can carry different data. This is the feature that turns an enum from a glorified integer into one of the most-used tools in the language. A variant comes in one of three shapes, and they mirror the three kinds of struct you met in III.06. Run this:

// Variants are not just labels: each one can carry its own data, and the
// three shapes a variant can take cover every case you will ever need.
enum Event {
    // unit-like: a label with nothing attached
    Tick,
    // tuple-like: positional fields, like a tuple struct
    KeyPress(char),
    // struct-like: named fields, like a struct
    Click { x: i32, y: i32 },
}

fn describe(event: &Event) -> String {
    match event {
        Event::Tick => "the clock ticked".to_string(),
        Event::KeyPress(c) => format!("key {c:?} was pressed"),
        Event::Click { x, y } => format!("click at ({x}, {y})"),
    }
}

fn main() {
    let events = [
        Event::Tick,
        Event::KeyPress('q'),
        Event::Click { x: 10, y: 20 },
    ];
    for event in &events {
        println!("{}", describe(event));
    }
}

Three variants, three shapes. Tick is unit-like: a bare label with nothing attached, just like Light::Red above. KeyPress(char) is tuple-like: it holds positional fields, exactly like a tuple struct, so a KeyPress always comes with a char inside it. Click { x, y } is struct-like: it holds named fields, like a regular struct, so a Click always comes with an x and a y. One enum, three internal shapes, and the data each variant needs travels with it.

Notice how describe reaches the data. The match does double duty: it picks the variant and, in the same breath, binds the data that variant carries. Event::KeyPress(c) names the inner char as c; Event::Click { x, y } names the two fields as x and y. You cannot reach a variant’s data without first establishing which variant you have, which is the whole point: the data only exists in some cases, so the language makes you handle the case before it hands you the data.

This is the deep reason enumis everywhere in Rust. The standard library is full of them. A web framework’s request method, a parser’s token, the JSON node from the first paragraph: each is one type with a fixed set of variants, each variant carrying precisely the data that case needs and no other. The full grammar for taking these apart, the patterns that destructure nested variants, is the very next chapter, III.08. Here it is enough to see that the data is in there and a match arm can name it.

Here is the idea that gives the chapter its title, and it is worth slowing down for, because it reframes everything you already know about structs. Think about how many distinct values a type can hold. A struct with a bool field and a field that is one of three colours can hold 2 times 3, which is 6 distinct values: every bool paired with every colour. You multiply the choices, because the struct holds all of its fields at once. A struct is a product type: its size in possible values is the product of its fields’.

An enum is the other arithmetic. A type that is a bool in one variant or one of three colours in another can hold 2 plus 3, which is 5 distinct values: every bool, then every colour, never both. You add the choices, because the enum holds exactly one variant at a time. An enum is a sum type: its size in possible values is the sum of its variants’. That is the literal meaning of algebraic data type: a type built by adding (enum) and multiplying (struct) other types together. The arithmetic is not a metaphor; it is the count of values each construct can represent.

Hold the two side by side. A struct is an and: a name and an age and an address, all present together. An enum is an or: red or yellow or green, exactly one of them. Most languages give you the and (structs, records, classes) but only a weak or (an integer tag you interpret by hand, or a class hierarchy). Rust gives you a real, first-class or, and pairs it with a match that forces you to address every branch of it.

Back in I.03 the slogan was make illegal states unrepresentable: design your types so that a value the program should never hold cannot even be constructed. That was a promise about a tool you had not met yet. The sum type is the tool, and now you can cash the slogan in.

Picture a network connection. It is in one of three states: disconnected, connecting (on some attempt number), or connected (to some address). The lazy modelling reaches for a struct that holds a flag and every field any state might need. Run this and watch the problem appear:

// A struct is a PRODUCT: every field is present at once.
// This one can describe nonsense: a connection that is both live and retrying.
struct LooseConnection {
    connected: bool,
    address: Option<String>,
    retry_count: u32,
}

// An enum is a SUM: exactly one variant is present at a time.
// Each state carries only the data that state actually has, and no other
// combination can even be written down.
enum Connection {
    Disconnected,
    Connecting { attempt: u32 },
    Connected { address: String },
}

fn status(conn: &Connection) -> String {
    match conn {
        Connection::Disconnected => "offline".to_string(),
        Connection::Connecting { attempt } => format!("dialing, try {attempt}"),
        Connection::Connected { address } => format!("online at {address}"),
    }
}

fn main() {
    // The loose struct lets you build a contradiction the compiler accepts:
    let nonsense = LooseConnection {
        connected: true,
        address: None,
        retry_count: 9,
    };
    println!("loose struct allows: connected={} addr={:?} retries={}",
        nonsense.connected, nonsense.address, nonsense.retry_count);

    // The enum cannot. Each state is one variant, with exactly its own data:
    let states = [
        Connection::Disconnected,
        Connection::Connecting { attempt: 2 },
        Connection::Connected { address: "10.0.0.1:443".to_string() },
    ];
    for conn in &states {
        println!("{}", status(conn));
    }
}

Look at LooseConnection. Because a struct is a product, every field is present at once, so the type can describe states that make no sense. The value built in main claims to be connected: true with address: None and a retry_count of 9: online, with no address, while still retrying. That is a contradiction, and the compiler accepts it without complaint, because nothing in the type says those fields constrain each other. Every function that touches a LooseConnection now has to defend against combinations that should never occur.

Now look at Connection. It is a sum: exactly one variant at a time, and each variant carries only the data that state actually has. Disconnected carries nothing. Connecting carries the attempt number and nothing else. Connected carries the address and nothing else. There is no field for an address on a disconnected value, so a disconnected value with an address is not a bug you guard against; it is a sentence you cannot write. The contradiction LooseConnection allowed is gone, not because you remembered to check, but because the type has no room to hold it.

In Part I you met Option<T> as the answer to null: a value that is either Some(value) or None. It probably felt like special syntax, a built-in feature of the language. It is not. Option is an ordinary enum defined in the standard library, with a type parameter T for whatever it might hold, and you now have everything you need to read its definition. It is, almost exactly, this:

// Option is not magic syntax. It is an ordinary enum from the standard
// library, with a type parameter T for whatever it might hold. Here we write
// our own copy to show there is nothing hidden inside it.
enum Maybe<T> {
    Just(T),
    Nothing,
}

fn first_even(numbers: &[i32]) -> Maybe<i32> {
    for &n in numbers {
        if n % 2 == 0 {
            return Maybe::Just(n);
        }
    }
    Maybe::Nothing
}

fn main() {
    // Our hand-built Maybe behaves just like the real Option.
    match first_even(&[1, 3, 4, 7]) {
        Maybe::Just(n) => println!("our Maybe found {n}"),
        Maybe::Nothing => println!("our Maybe found nothing"),
    }

    // And the real Option is exactly this enum, already in std:
    let real: Option<i32> = [1, 3, 5].iter().copied().find(|n| n % 2 == 0);
    match real {
        Some(n) => println!("std Option found {n}"),
        None => println!("std Option found nothing"),
    }
}

The hand-built Maybe<T> at the top is Option with the names changed. Just(T) is Some(T), a tuple-like variant carrying one value of the generic type. Nothing is None, a unit-like variant carrying nothing. The real Option in std is literally enum Option<T> { Some(T), None }, the same two-variant sum type, and the program proves it by using both the home-made and the standard version the same way. Everything you learned about Option in Part I, that you must handle None before you reach the value, that the variant comes with its data, is just what an enum is.

The same is true of Result<T, E> from I.02. It is an enum too, with two variants that each carry data: Ok(T) and Err(E). The whole errors-as-values story from that chapter was built on a sum type all along; you just had not been shown the floorboards yet. Methods like unwrap_or and combinators like map are ordinary functions written in an impl block on these enums, which is exactly what the next section shows you how to do yourself.

An enum is a type, and in III.06 you learned that types get behaviour through impl blocks. Nothing changes for enums: you write impl Shape, give it methods that take self (or &self, or &mut self), and the method body matches on which variant self is. Run this:

// An enum is a type, so it can carry methods through impl, exactly like the
// structs from III.06. The method takes self and matches on its own variants.
enum Shape {
    Circle { radius: f64 },
    Rectangle { width: f64, height: f64 },
    Triangle { base: f64, height: f64 },
}

impl Shape {
    // Borrow self, look at which variant we are, compute from its fields.
    fn area(&self) -> f64 {
        match self {
            Shape::Circle { radius } => std::f64::consts::PI * radius * radius,
            Shape::Rectangle { width, height } => width * height,
            Shape::Triangle { base, height } => 0.5 * base * height,
        }
    }

    // An associated function (no self) that builds a variant: a tidy
    // constructor that hides which variant a "unit square" really is.
    fn unit_square() -> Shape {
        Shape::Rectangle { width: 1.0, height: 1.0 }
    }
}

fn main() {
    let shapes = [
        Shape::Circle { radius: 2.0 },
        Shape::Rectangle { width: 3.0, height: 4.0 },
        Shape::Triangle { base: 6.0, height: 2.0 },
        Shape::unit_square(),
    ];
    let mut total = 0.0;
    for shape in &shapes {
        let a = shape.area();
        println!("area = {a:.3}");
        total += a;
    }
    println!("total area = {total:.3}");
}

area takes &self, borrowing the shape without consuming it, exactly as a struct method would. The body is a match on self: it figures out which variant this Shapeis, binds that variant’s fields, and computes from them. A Circle reads its radius; a Rectangle reads its width and height; a Triangle reads its base and height. One method, one formula per variant, dispatched by the match. This pairing of a sum type with a method that matches on it is the single most common shape in idiomatic Rust, and you will write it constantly.

unit_square shows the other kind of function in an impl: an associated function, one with no self parameter, called as Shape::unit_square(). It builds and returns a variant, which makes it a tidy constructor. Callers get a unit square without having to know or care that it is really a Rectangle under the hood. That is a small but real benefit: the variant a constructor chooses is an implementation detail it can hide.

You do not need to know an enum’s memory layout to use one, but a rough picture pays off later, when you care about size and performance, and it dispels any worry that variants carrying data must be expensive. The idea is simple. An enum value is a small tag (a number saying which variant this is) plus enough room for the largest variant’s data. It is not the sum of all the variants’ sizes; every value of the enum is one size, big enough for whichever variant happens to be the roomiest. Run this and read the numbers:

// An enum value is a TAG (which variant) plus enough room for the LARGEST
// variant. So the size is not the sum of the variants; it is the biggest one,
// plus a little for the tag, rounded up for alignment.
use std::mem::size_of;

enum Packet {
    Ack,                       // carries nothing
    Seq(u32),                  // carries 4 bytes
    Payload { bytes: [u8; 64] }, // carries 64 bytes: the largest variant
}

// How many bytes of payload each variant actually carries. The match reads the
// data out of each variant, which also proves the data is really there.
fn payload_len(packet: &Packet) -> usize {
    match packet {
        Packet::Ack => 0,
        Packet::Seq(_n) => 4,
        Packet::Payload { bytes } => bytes.len(),
    }
}

fn main() {
    // Build one of each variant. Whatever payload a Packet carries, every value
    // still sits in the same number of bytes in memory.
    let packets = [Packet::Ack, Packet::Seq(7), Packet::Payload { bytes: [0; 64] }];
    for packet in &packets {
        println!("this packet carries {} bytes of payload", payload_len(packet));
    }

    // The whole enum is sized for its biggest variant plus the tag, not for
    // the sum of all three.
    println!("size_of::<Packet>()      = {}", size_of::<Packet>());
    println!("size_of::<[u8; 64]>()    = {}", size_of::<[u8; 64]>());

    // The niche optimisation: a reference can never be null, so the compiler
    // reuses that impossible all-zero bit pattern to mean None. That makes
    // Option<&T> the same size as &T, with no separate tag byte at all.
    println!("size_of::<&u32>()        = {}", size_of::<&u32>());
    println!("size_of::<Option<&u32>>() = {}", size_of::<Option<&u32>>());
}

Packet has a variant carrying nothing, one carrying a 4-byte u32, and one carrying a 64-byte array. The whole enum prints as 68 bytes: the 64-byte array (the largest variant) plus room for the tag, rounded up for alignment. Crucially it is not 0 plus 4 plus 64; the variants share the space, because only one is ever live at a time. An Ack, which carries nothing, still occupies the full Packet size, because every Packet must fit in the same slot whatever variant it holds.

The last two lines show a lovely optimisation. A reference like &u32 can never be null; its all-zero bit pattern is an impossible value. The compiler notices that impossible pattern is going spare and reuses it to mean None. So Option<&u32> is the same size as &u32, with no separate tag byte at all: both print 8. This is the niche optimisation (a niche being a bit pattern a type can never legally hold), and it is why wrapping a reference in Optionto express "maybe a reference" costs you nothing in space. Absence is free here, exactly where in C you would have paid with a real null pointer and the danger that comes with it.

One example to tie it together, on the problem sum types were almost born for: a tree. An arithmetic expression is, by its nature, exactly one of a few shapes. It is a number, or the sum of two sub-expressions, or a product of two, or the negation of one. That oris a sum type, and the "sub-expression" inside each variant is another Expr, so the type refers to itself. Run it:

// A small worked example: a tiny expression tree, the classic place where a
// sum type earns its keep. An Expr is exactly one of these shapes, and eval
// walks the tree by matching on self.
enum Expr {
    Number(f64),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Neg(Box<Expr>),
}

impl Expr {
    fn eval(&self) -> f64 {
        match self {
            Expr::Number(n) => *n,
            Expr::Add(a, b) => a.eval() + b.eval(),
            Expr::Mul(a, b) => a.eval() * b.eval(),
            Expr::Neg(inner) => -inner.eval(),
        }
    }
}

fn main() {
    // Build  -(2 + 3) * 4  as a tree of variants.
    let expr = Expr::Mul(
        Box::new(Expr::Neg(Box::new(Expr::Add(
            Box::new(Expr::Number(2.0)),
            Box::new(Expr::Number(3.0)),
        )))),
        Box::new(Expr::Number(4.0)),
    );
    println!("result = {}", expr.eval());
}

Every idea in the chapter is here in eighteen lines. Expr is a sum type: an expression is exactly one of Number, Add, Mul, or Neg, never two at once. Each variant carries precisely the data that case needs: Number carries one f64, Add and Mul carry two sub-expressions each, Neg carries one. The eval method lives in an impl block, takes &self, and matches on the variant, calling itself on the sub-expressions until it bottoms out at the numbers. The tree for -(2 + 3) * 4 evaluates to -20, computed by walking the variants.

The one new face is Box. A variant cannot hold a bare Expr directly here, because then an Expr would contain an Expr would contain an Expr with no bottom, and the compiler could not give it a finite size. Box<Expr> puts the child on the heap and stores a fixed-size pointer to it, which breaks the cycle. Box is a Part IV story and you will meet it properly there; for now read Box<Expr> as "a pointer to another Expr" and let the recursion read naturally.

What comes next is the other half of every example in this chapter. You have seen enums defined, given data, and given methods, and every single time the way back into a variant was match. The next chapter, III.08, is about match and the full pattern grammar in its own right: nested patterns, guards, ranges, bindings, and the rules that make a match exhaustive. The sum type and the pattern are two halves of one tool. You have the first half now.