Algebraic Data Types: Sum and Product Types
The term 'algebraic' isn't marketing fluff—it's literal. Types form an algebra where you can count the number of possible values (cardinality) and combine types using operations analogous to...
Key Insights
- Algebraic data types combine product types (AND—structs, tuples) and sum types (OR—tagged unions, enums with data) to model domains precisely, with cardinality calculated by multiplication and addition respectively.
- The real power of ADTs emerges through exhaustive pattern matching, which forces you to handle every possible case and catches bugs at compile time rather than runtime.
- By designing types where invalid states are unrepresentable, you eliminate entire categories of bugs and make your code’s intent explicit in the type system itself.
What Makes Data Types “Algebraic”
The term “algebraic” isn’t marketing fluff—it’s literal. Types form an algebra where you can count the number of possible values (cardinality) and combine types using operations analogous to multiplication and addition.
Consider a boolean: it has exactly 2 possible values. A byte has 256. When you combine types, the math is straightforward. A struct containing a boolean AND a byte has 2 × 256 = 512 possible values. A union that’s either a boolean OR a byte has 2 + 256 = 258 possible values.
This matters because precise types mean precise constraints. Compare these two approaches to representing a user’s subscription status:
# Stringly-typed: infinite possible values, most invalid
user_status = "premium" # or "freemium"? "Premium"? "PREMIUM"? "prem"?
# ADT approach: exactly 3 possible values
from enum import Enum
class SubscriptionStatus(Enum):
FREE = "free"
PREMIUM = "premium"
ENTERPRISE = "enterprise"
The stringly-typed version accepts infinite strings. The ADT version accepts exactly three values. The compiler becomes your ally, rejecting typos and invalid states before your code ever runs.
Product Types: Combining Values with “AND”
Product types bundle multiple values together. You need ALL the components to construct the type. Structs, tuples, records, and classes are all product types.
The cardinality is the product of each field’s cardinality. A type with a boolean (2 values) and a three-variant enum (3 values) has 2 × 3 = 6 possible values.
// Rust struct: a product type
struct User {
id: u32, // 2^32 possible values
active: bool, // 2 possible values
role: Role, // 3 possible values (assuming 3 variants)
}
// Total: 2^32 × 2 × 3 possible User values
// TypeScript interface: a product type
interface User {
id: number;
email: string;
createdAt: Date;
}
# Python dataclass: a product type
from dataclasses import dataclass
from datetime import datetime
@dataclass
class User:
id: int
email: str
created_at: datetime
Product types are the workhorses of programming. Every time you group related data, you’re creating a product type. The key insight is recognizing that the number of possible values grows multiplicatively—which is why keeping individual field types constrained matters.
Sum Types: Representing Alternatives with “OR”
Sum types represent values that can be one of several variants—but only one at a time. Tagged unions, discriminated unions, and enums with associated data are all sum types.
The cardinality is the sum of each variant’s cardinality. A type that’s either a boolean (2 values) OR a three-variant enum (3 values) has 2 + 3 = 5 possible values.
// Rust's Option: the canonical sum type
enum Option<T> {
Some(T), // cardinality of T
None, // cardinality of 1
}
// Total: T + 1 possible values
// Rust's Result: sum type for error handling
enum Result<T, E> {
Ok(T), // cardinality of T
Err(E), // cardinality of E
}
// Total: T + E possible values
// Custom sum type
enum PaymentMethod {
CreditCard { number: String, expiry: String, cvv: String },
BankTransfer { account: String, routing: String },
Crypto { wallet_address: String },
}
// TypeScript discriminated union: sum type via literal types
type ApiResponse<T> =
| { status: "loading" }
| { status: "success"; data: T }
| { status: "error"; message: string };
-- Haskell: where ADTs originated
data Maybe a = Nothing | Just a
data Either a b = Left a | Right b
data PaymentMethod
= CreditCard String String String
| BankTransfer String String
| Crypto String
Sum types shine when modeling states that are mutually exclusive. A network request is loading OR successful OR failed—never multiple simultaneously. A payment is via card OR bank transfer OR crypto—never a hybrid.
Pattern Matching: Unlocking ADT Power
Pattern matching is what transforms ADTs from a nice organizational tool into a bug-prevention system. The compiler verifies you’ve handled every possible case.
fn process_payment(method: PaymentMethod) -> Result<Receipt, PaymentError> {
match method {
PaymentMethod::CreditCard { number, expiry, cvv } => {
validate_card(&number, &expiry, &cvv)?;
charge_card(&number, amount)
}
PaymentMethod::BankTransfer { account, routing } => {
initiate_ach_transfer(&account, &routing, amount)
}
PaymentMethod::Crypto { wallet_address } => {
send_crypto_invoice(&wallet_address, amount)
}
}
}
Add a new payment method—say PaymentMethod::PayPal { email: String }—and the compiler immediately flags every match statement that doesn’t handle it. This is exhaustiveness checking, and it’s transformative for maintenance.
function renderResponse<T>(response: ApiResponse<T>): string {
switch (response.status) {
case "loading":
return "Loading...";
case "success":
return `Data: ${JSON.stringify(response.data)}`;
case "error":
return `Error: ${response.message}`;
// TypeScript will error if you miss a case (with strict settings)
}
}
The pattern matching also destructures values, giving you access to the associated data only when it’s guaranteed to exist. You can’t accidentally access response.data when status is "error"—the type system prevents it.
Practical Modeling: Eliminating Impossible States
The most valuable application of ADTs is making invalid states unrepresentable. If your type system can’t express a bug, you can’t write that bug.
Consider a common anti-pattern—boolean flags for mutually exclusive states:
// BAD: Boolean flags allow impossible states
interface RequestState {
isLoading: boolean;
isError: boolean;
isSuccess: boolean;
data?: User;
errorMessage?: string;
}
// What does this mean?
const broken: RequestState = {
isLoading: true,
isError: true,
isSuccess: true,
data: undefined,
errorMessage: "wat"
};
// The type allows it. The logic doesn't.
This type has 2 × 2 × 2 × (User | undefined) × (string | undefined) possible values—most of which are nonsensical. Now compare:
// GOOD: Sum type makes invalid states unrepresentable
type RequestState<T> =
| { status: "idle" }
| { status: "loading" }
| { status: "success"; data: T }
| { status: "error"; message: string };
// Only valid combinations are expressible
const valid: RequestState<User> = {
status: "success",
data: { id: 1, name: "Alice" }
};
// This won't compile:
// const invalid: RequestState<User> = {
// status: "loading",
// data: someUser // Error: 'data' does not exist on loading state
// };
The refactored type has exactly 1 + 1 + |User| + |string| possible values—all valid. You’ve eliminated bugs by making them inexpressible.
ADTs Across Languages
Some languages have first-class ADT support. Others require patterns and conventions to approximate them.
Native support:
// Rust: Excellent ADT support
enum Shape {
Circle { radius: f64 },
Rectangle { width: f64, height: f64 },
}
fn area(shape: &Shape) -> f64 {
match shape {
Shape::Circle { radius } => std::f64::consts::PI * radius * radius,
Shape::Rectangle { width, height } => width * height,
}
}
-- Haskell: ADTs are foundational
data Shape = Circle Double | Rectangle Double Double
area :: Shape -> Double
area (Circle r) = pi * r * r
area (Rectangle w h) = w * h
Emulation patterns:
// TypeScript: Discriminated unions
type Shape =
| { kind: "circle"; radius: number }
| { kind: "rectangle"; width: number; height: number };
function area(shape: Shape): number {
switch (shape.kind) {
case "circle":
return Math.PI * shape.radius ** 2;
case "rectangle":
return shape.width * shape.height;
}
}
# Python 3.10+: Structural pattern matching with dataclasses
from dataclasses import dataclass
from typing import Union
import math
@dataclass
class Circle:
radius: float
@dataclass
class Rectangle:
width: float
height: float
Shape = Union[Circle, Rectangle]
def area(shape: Shape) -> float:
match shape:
case Circle(radius=r):
return math.pi * r * r
case Rectangle(width=w, height=h):
return w * h
TypeScript’s discriminated unions require discipline—you must include a literal discriminant field and use switch statements consistently. Python’s approach is newer and less battle-tested, but the pattern matching syntax is clean.
When to Reach for ADTs
ADTs aren’t always the answer. They excel in specific scenarios:
State machines: Any time you have distinct states with different associated data. UI loading states, order fulfillment stages, authentication flows.
API responses: Success and error cases naturally model as sum types. The associated data differs based on the outcome.
Domain modeling: When your domain has “a thing that’s either X or Y,” that’s a sum type. Payment methods, notification channels, user roles with different permissions.
Replacing nullable fields: If a field only makes sense in certain states, that’s a signal to use a sum type instead of optional fields.
The trade-offs are real. Languages without native ADT support require more boilerplate. Team members unfamiliar with the pattern face a learning curve. And over-engineering simple cases with elaborate type hierarchies adds complexity without benefit.
But when you’re modeling genuinely complex domains, ADTs pay dividends. Bugs become compile errors. Intent becomes explicit. And the next developer reading your code understands not just what states exist, but that those are the only states that can exist.
Start with your next state machine or API response type. Model it as a sum type with exhaustive pattern matching. Watch the compiler catch the edge case you would have forgotten. That’s when ADTs click.