Recursive Enum Variants for List Operations

Snippet

Recursive Enum Variants for List Operations

Recursive enums enable elegant linked list implementations where each variant can contain itself. Box<T> is essential here because the compiler needs to know the size of each variant at compile time, and a recursive type without indirection would have infinite size. The Cons variant holds data plus a boxed pointer to the next element, while Nil serves as the terminal case. This pattern demonstrates how Rust's type system naturally expresses recursive data structures while maintaining memory safety through heap allocation.

snippet.rs
rust
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}
 
impl<T> List<T> {
    fn new() -> Self { List::Nil }
 
    fn prepend(self, elem: T) -> Self {
        List::Cons(elem, Box::new(self))
    }
 
    fn len(&self) -> usize {
        match self {
            List::Cons(_, tail) => 1 + tail.len(),
            List::Nil => 0,
        }
    }
 
    fn map<U, F>(self, f: F) -> List<U>
    where F: FnOnce(T) -> U {
        match self {
            List::Cons(head, tail) => f(head).prepend(*tail.map(f)),
            List::Nil => List::Nil,
        }
    }
}
 
fn main() {
    let list = List::Nil
        .prepend(3)
        .prepend(2)
        .prepend(1);
    println!("Length: {}", list.len());
    let doubled = list.map(|x| x * 2);
}

Breakdown

enum List<T> {

Generic enum declaration with type parameter T

Cons(T, Box<List<T>>),

Cons holds value and pointer to next element

Nil,

Terminal variant representing empty list

fn prepend(self, elem: T) -> Self {

Consume self to create new list with element at front

1 + tail.len()

Recursive call traverses list counting elements

Previous snippet Next snippet

More Intermediate Rust exercises →

From your library

Recursive Enum Variants for List Operations

Related