Algebraic Data Types & Pattern Matching in Python

How dataclass, Enum, and match model the domain so that invalid states are structurally impossible.

1. What Are Algebraic Data Types?

There are exactly two building blocks from which all data structures are composed:

Product Types (AND combination): A value has property A and property B
Sum Types (OR combination): A value is either variant A or variant B

"The canonical implementation of a product of two types in a programming language is a pair." — Category Theory for Programmers, p. 96

"A choice type like this is called a discriminated union in F#." — Domain Modeling Made Functional, p. 77

Why "Algebraic"?

Because these types behave like algebra. Product types multiply the possible values, sum types add them:

# Product Type: Bool × Bool = 2 × 2 = 4 possible values
# (True, True), (True, False), (False, True), (False, False)

# Sum Type: Bool + Bool = 2 + 2 = 4 possible values
# Left(True), Left(False), Right(True), Right(False)

"We've seen two commutative monoidal structures underlying the type system: We have the sum types with Void as the neutral element, and the product types with the unit type, (), as the neutral element." — Category Theory for Programmers, p. 106

This is a tool for precisely controlling the number of possible states.

2. Product Types: Bundling Things Together

A product type bundles multiple values into one. In Python, the most natural tool is the dataclass with frozen=True:

from dataclasses import dataclass

@dataclass(frozen=True)
class Customer:
    name: str
    email: str
    age: int

frozen=True makes the instance immutable — in the spirit of functional programming.

Why Not Just a Dict?

# ❌ Dict: No guarantees
customer = {"name": "Alice", "email": "alice@example.com"}
# Where is "age"? Typo in "emial"? No error at definition time.

# ✅ Dataclass: Structure is clear
alice = Customer(name="Alice", email="alice@example.com", age=30)
# Missing fields → TypeError. Typos → immediately visible.

Nested Product Types

@dataclass(frozen=True)
class Address:
    street: str
    city: str
    zip_code: str

@dataclass(frozen=True)
class CustomerWithAddress:
    name: str
    email: str
    address: Address

Tuples as Lightweight Product Types

from typing import NamedTuple

class Point(NamedTuple):
    x: float
    y: float

origin = Point(0.0, 0.0)
print(origin.x)  # 0.0

3. Sum Types: Modeling Either-Or

A sum type says: A value is exactly one of several variants.

Simple Sum Types with Enum

from enum import Enum, auto

class Color(Enum):
    RED = auto()
    GREEN = auto()
    BLUE = auto()

A Color value is always exactly one of the three defined values. No fourth state, no None.

Sum Types with Data: The Payment Case

@dataclass(frozen=True)
class CreditCard:
    number: str
    expiry: str
    cvv: str

@dataclass(frozen=True)
class PayPal:
    email: str

@dataclass(frozen=True)
class BankTransfer:
    iban: str
    bic: str

Payment = CreditCard | PayPal | BankTransfer

4. Pattern Matching with `match/case`

Python 3.10 introduced structural pattern matching. It allows processing sum types elegantly and safely:

def describe_payment(payment: Payment) -> str:
    match payment:
        case CreditCard(number=num):
            masked = "****" + num[-4:]
            return f"Credit card {masked}"
        case PayPal(email=email):
            return f"PayPal ({email})"
        case BankTransfer(iban=iban):
            return f"Bank transfer to {iban}"

"Pattern matching is a natural fit for functional programming." — Functional Anthology, p. 218

Guards: Additional Conditions

def shipping_cost(weight_kg: float) -> float:
    match weight_kg:
        case w if w <= 0:
            raise ValueError("Weight must be positive")
        case w if w <= 1.0:
            return 4.99
        case w if w <= 5.0:
            return 7.99
        case w if w <= 20.0:
            return 12.99
        case _:
            return 24.99

Nested Patterns

@dataclass(frozen=True)
class Order:
    customer: str
    payment: Payment
    amount: float

def validate_order(order: Order) -> str:
    match order:
        case Order(amount=a) if a <= 0:
            return "Invalid amount"
        case Order(payment=CreditCard(number=num)) if len(num) != 16:
            return "Invalid card number"
        case Order(payment=BankTransfer(iban=iban)) if not iban.startswith("DE"):
            return "Only German IBANs allowed"
        case Order(customer=name, amount=amount):
            return f"Order from {name} for {amount:.2f}€ is valid"

5. Making Illegal States Unrepresentable

The most powerful idea behind ADTs:

"Make Invalid States Unrepresentable is a design guideline that suggests modeling the types and data structures in such a way that it's impossible, or at least difficult, to represent a state that is not valid within the domain." — Haskell Pragmatic Type-Level Design, p. 89

❌ The Problem: Flags and Optional Fields

@dataclass
class EmailContact:
    email: str
    is_verified: bool
    verified_at: str | None = None

Nothing prevents an inconsistent state:

broken = EmailContact("test@example.com", is_verified=True, verified_at=None)
also_broken = EmailContact("test@example.com", is_verified=False, verified_at="2024-01-01")

✅ The Solution: Sum Type Instead of Flags

"We converted a design with a flag into a design with two choices, one for each state: 'Unverified' and 'Verified.'" — Domain Modeling Made Functional, p. 134

@dataclass(frozen=True)
class UnverifiedEmail:
    email: str

@dataclass(frozen=True)
class VerifiedEmail:
    email: str
    verified_at: str

EmailStatus = UnverifiedEmail | VerifiedEmail

Now an inconsistent state cannot exist: - UnverifiedEmail has no verified_at → cannot be accidentally set - VerifiedEmail always has a verified_at → cannot be forgotten

Order Status as State Machine

"By using state machines for these cases, each state can have different allowable behavior." — Domain Modeling Made Functional, p. 136

@dataclass(frozen=True)
class Draft:
    items: tuple[str, ...]

@dataclass(frozen=True)
class Submitted:
    items: tuple[str, ...]
    submitted_at: str

@dataclass(frozen=True)
class Paid:
    items: tuple[str, ...]
    submitted_at: str
    paid_at: str
    transaction_id: str

@dataclass(frozen=True)
class Shipped:
    items: tuple[str, ...]
    tracking_number: str

@dataclass(frozen=True)
class Cancelled:
    reason: str

OrderStatus = Draft | Submitted | Paid | Shipped | Cancelled

Each state transition becomes a function that accepts only the correct input state:

def submit_order(draft: Draft, timestamp: str) -> Submitted:
    if not draft.items:
        raise ValueError("Empty order cannot be submitted")
    return Submitted(items=draft.items, submitted_at=timestamp)

def pay_order(submitted: Submitted, timestamp: str, txn_id: str) -> Paid:
    return Paid(
        items=submitted.items,
        submitted_at=submitted.submitted_at,
        paid_at=timestamp,
        transaction_id=txn_id,
    )

def cancel_order(order: Draft | Submitted, reason: str) -> Cancelled:
    return Cancelled(reason=reason)

cancel_order only accepts Draft | Submitted. A paid or shipped order cannot structurally be cancelled.

6. Result Type: Error Handling Without Exceptions

One of the most important applications of sum types — explicit error handling:

"While Optional represents a kind of container that can either be empty or contain an object of type T, there might be a case when the container is never empty and contains a value of type A or a value of type B. This data type is Either." — FP in Kotlin by Tutorials, p. 240

from typing import Generic, TypeVar

T = TypeVar("T")
E = TypeVar("E")

@dataclass(frozen=True)
class Ok(Generic[T]):
    value: T

@dataclass(frozen=True)
class Err(Generic[E]):
    error: E

Result = Ok[T] | Err[E]

Application: User Validation

def validate_user(name: str, email: str, age: int) -> Ok[User] | Err[ValidationError]:
    if not name.strip():
        return Err(ValidationError("name", "Name must not be empty"))
    if "@" not in email:
        return Err(ValidationError("email", "Invalid email address"))
    if age < 0 or age > 150:
        return Err(ValidationError("age", "Invalid age"))
    return Ok(User(name=name.strip(), email=email.lower(), age=age))

def greet_user(result: Ok[User] | Err[ValidationError]) -> str:
    match result:
        case Ok(value=user):
            return f"Welcome, {user.name}!"
        case Err(error=err):
            return f"Error in '{err.field}': {err.message}"

Advantages over exceptions: - The return type documents that something can go wrong - The caller must deal with the error case - No invisible control flow

7. Practical Example: Form Processing

Everything combined — a registration form with multiple validation steps:

@dataclass(frozen=True)
class FormInput:
    username: str
    email: str
    password: str
    password_confirm: str

@dataclass(frozen=True)
class ValidatedForm:
    username: str
    email: str
    password_hash: str

FormError = EmptyField | InvalidEmail | PasswordMismatch | PasswordTooShort

Each validation is a pure function with the signature str → Ok[str] | Err[FormError]:

def check_not_empty(value: str, field_name: str) -> Ok[str] | Err[EmptyField]:
    if value.strip():
        return Ok(value.strip())
    return Err(EmptyField(field_name))

def check_email(email: str) -> Ok[str] | Err[InvalidEmail]:
    if "@" in email and "." in email.split("@")[-1]:
        return Ok(email.lower())
    return Err(InvalidEmail(email))

def check_passwords_match(pw: str, confirm: str) -> Ok[str] | Err[PasswordMismatch]:
    if pw == confirm:
        return Ok(pw)
    return Err(PasswordMismatch())

What Was Achieved?

Every possible error has its own type — no generic ValueError("something")
All validations are pure functions — testable, composable, no side effects
Pattern matching enforces completeness — every error case must be handled
No exceptions — control flow is always visible

Try it yourself

from dataclasses import dataclass

@dataclass(frozen=True)
class Ok:
    value: object

@dataclass(frozen=True)
class Err:
    error: str

def parse_age(raw: str) -> Ok | Err:
    if not raw.strip():
        return Err("age must not be empty")
    if not raw.isdigit():
        return Err(f"'{raw}' is not a number")
    age = int(raw)
    if age < 0 or age > 150:
        return Err(f"invalid age: {age}")
    return Ok(age)

def describe(result: Ok | Err) -> str:
    match result:
        case Ok(value=age):
            return f"OK – age: {age}"
        case Err(error=msg):
            return f"Error: {msg}"

for raw in ["42", "", "abc", "200", "0"]:
    print(f"{raw!r:>6} → {describe(parse_age(raw))}")

Try extending parse_age with an additional rule (e.g. minimum age 18) — without breaking the signature.

Which statement about algebraic data types (ADTs) and pattern matching in Python is *false*?

Summary

Concept	Python Tool	Purpose
Product Type	`@dataclass(frozen=True)`	Bundle data (AND)
Sum Type	`X \\| Y \\| Z` (Union)	Model variants (OR)
Pattern Matching	`match/case`	Safely process sum types
Enum	`enum.Enum`	Simple finite sets
Result Type	`Ok[T] \\| Err[E]`	Explicit error handling

The key insight: When the possible states of data are constrained with ADTs, entire categories of bugs disappear.

In the next article, we take the decisive step further: These data structures are functors and monads — and that allows shifting complexity from business logic into the data structures themselves.

Sources

Bartosz Milewski, Category Theory for Programmers, pp. 95–106
Scott Wlaschin, Domain Modeling Made Functional, pp. 77, 111–122, 124–136
Alexander Granin, Haskell Pragmatic Type-Level Design, p. 89
FP in Kotlin by Tutorials, pp. 240–260
Functional Anthology, pp. 111, 218–222
Michael Bevilacqua-Linn, Functional Patterns, pp. 27, 82

Code

src/product_types.py – Dataclasses and NamedTuples
src/sum_types.py – Enum, Union Types, Payment example
src/pattern_matching.py – Match/Case, Guards, nested patterns
src/illegal_states.py – Making Illegal States Unrepresentable
src/result_type.py – Result type and error handling
src/form_validation.py – Practical example: form processing