Sum Types: From ML to Rust and Swift

Hello! Welcome back to our course on programming theory.

In our previous lesson, we explored product types—like tuples and records—which model data using an "and" relationship, corresponding to the mathematical concept of a Cartesian product. We traced this idea from its practical implementation in the ML language family back to its formal roots in type theory.

Today, we'll investigate the other half of algebraic data types: sum types. This lesson directly addresses the learning outcome: Define sum types using variants or tagged unions, from their origins in ML through modern implementations in Rust and Swift.

Where product types represent combinations, sum types represent choices. We will define what a sum type is, trace its fascinating history from early functional languages, explore powerful patterns it enables, and see how it manifests in modern systems languages.

1. Defining Sum Types: The "Or" Relationship

A sum type defines a value that can be one of several different possibilities. Think of it as an "or" relationship: a value of a sum type is either an A or a B or a C.

Each possibility is called a variant. To distinguish which variant a value represents, each one is given a name or a "tag". This is why sum types are often called tagged unions or discriminated unions. The tag is crucial because it allows us to differentiate between variants even if they hold data of the same underlying type.

Let's start with a formal definition and some examples.

As the article notes, the simplest form of a sum type is an enumerated type, where the variants carry no data, like Red | Amber | Green.

The name "sum type," much like "product type," has mathematical origins related to the number of possible values (cardinality).

This property, that the total number of values is the sum of the number of values of the constituent types, is the source of the name. This is a direct consequence of the underlying set-theoretic model of a disjoint union.

2. The Origins and Evolution of Sum Types

The concept of a sum type evolved over several decades, with key contributions from pioneers in both imperative and functional programming. The ML language family and its predecessors were central to this story.

Let's start with a look at how algebraic data types, including sums, are defined in Standard ML, a direct descendant of the original ML.

The datatype declaration in ML is the direct ancestor of sum type definitions in many modern functional languages. To understand how we arrived here, let's trace the history more formally.

This historical path shows a clear progression:

• Mathematical Idea: McCarthy's abstract "direct union".
• Safety Concept: Hoare's "discriminated union" for compile-time safety.
• Language Formalization: Milner's ML giving it a name ("disjoint sum") and syntax.
• Modern Features: Burstall's HOPE adding tags and compiler-guaranteed exhaustiveness checking, a feature that makes sum types so robust in practice.

3. Canonical Use Cases: Option and Result

Beyond defining custom types like Tree, sum types are the foundation for some of the most powerful and common design patterns in modern typed functional programming. Two of the most important are for handling optional values and success/failure cases.

Let's explore these through the Maybe (often called Option) and Either (often called Result) types.

Let's break down why these patterns are so effective:

• Maybe a = Just a | Nothing
  This sum type elegantly solves the "billion-dollar mistake" of null references. Instead of a function returning a value or null (which is untyped and can be forgotten), a function returns a Maybe. The type system then forces the programmer to handle both the Just case (the value is present) and the Nothing case (it is absent). This makes the possibility of an absent value explicit and safe.

• Either e a = Left e | Right a
  This type models a computation that can have two outcomes. By convention, Right is used for the success case, holding a value of type a, and Left is used for the failure case, holding an error of type e. This is more descriptive than Maybe, as the Left variant can carry data about why the computation failed. In designing robust systems, like the financial platforms you've worked on, explicitly modeling all possible outcomes of an operation in the type system is a powerful technique for ensuring correctness.

4. Modern Implementations: Rust and Swift

The ideas pioneered in ML and Hope are now mainstream features in many modern languages, especially those focused on safety and correctness. Rust and Swift are prime examples. Both use the keyword enum for sum types, a term borrowed from C but supercharged with the capabilities of algebraic data types.

Rust
In Rust, enums are a cornerstone of the language, used for everything from the Option<T> and Result<T, E> types to modeling complex state.

// A classic sum type representing different kinds of web events.
enum WebEvent {
    // A variant with no data (a 'unit-like' struct).
    PageLoad,
    // A variant with unnamed data (a 'tuple' struct).
    KeyPress(char),
    // A variant with named data (a 'struct').
    Click { x: i64, y: i64 },
}

// Rust's version of Maybe/Option
enum Option<T> {
    None,
    Some(T),
}

// Rust's version of Either/Result
enum Result<T, E> {
    Ok(T),
    Err(E),
}

Notice how Rust's enum can have variants that are simple tags, contain tuples, or contain full-fledged structs.

Swift
Swift, used for Apple platform development, also has powerful enums with "associated values."

// An enum to represent different kinds of barcodes.
enum Barcode {
    // A variant with a tuple of four Ints.
    case upc(Int, Int, Int, Int)
    // A variant with a String.
    case qrCode(String)
}

// Swift's version of Maybe/Option is called `Optional`.
// It has special syntax: `String?` is sugar for `Optional<String>`.
enum Optional<Wrapped> {
    case none
    case some(Wrapped)
}

These modern implementations are direct descendants of the datatype from ML, demonstrating the lasting influence of these foundational concepts.

Conclusion

In this lesson, we have defined sum types and explored their role as a fundamental tool for data modeling in typed functional languages.

Key Takeaways:

• Sum Types represent an "or" relationship, where a value can be one of several variants. They are also known as tagged unions.
• The name "sum" comes from the fact that the total number of possible values is the sum of the cardinalities of the variants.
• The concept was formalized in the ML language family and refined in languages like HOPE, which introduced compiler-enforced exhaustiveness checking.
• Sum types enable powerful and safe design patterns, most notably Option/Maybe for handling optionality and Result/Either for error handling.
• Modern systems languages like Rust and Swift have adopted sum types (enum) as a core feature for building robust software.

Next Lesson Preview:

Defining product and sum types is only half the story. Their true power is unlocked by the mechanism used to consume them. In our next lesson, we will explore this mechanism: pattern matching. We will see how it provides safe and ergonomic control flow for deconstructing algebraic data types, and compare the classic ML-style matching with Python's recent addition of structural pattern matching.