Back to series
· 8 min read

Algebraic Data Types (ADTs)


1. What Are Algebraic Data Types

Algebraic data types (ADTs) are a type-system mechanism for building new types by combining existing ones.

The core idea is that complex data types can be assembled from simpler types in two basic ways:

  1. Product Type: a value contains several fields at once.
  2. Sum Type: a value can be one of several alternative types.

For example, a piece of user information may consist of a name, an age and an email — that is a product type; the result of a network request may be success, failure or loading — that is a sum type.

The essence of ADTs is not any particular data structure, but a way of modelling types.

From the perspective of type algebra:

  • A product type means several components exist simultaneously.
  • A sum type means choosing one among several alternative branches.
  • The two can be nested and combined to construct complex data models.

2. The Mathematical Foundations of Algebraic Data Types

The “algebraic” in ADT comes from the fact that types can be combined in ways analogous to arithmetic.

Suppose:

  • Type A has m possible values.
  • Type B has n possible values.

Then:

1. Product Types: Multiplication of Types

A product type describes a value made up jointly of several parts.

|A \times B| = |A| \cdot |B|

For example:

type User = {
  name: string;
  age: number;
};

If string has m possible values and number has n possible values, then in theory the value space of User is formed by the combinations of the two.

Every User value contains both name and age.

Structurally:

User
├── name: string
└── age: number

This structure is also called a record type.

Common product types include:

  • Tuples
  • Structs
  • Records
  • Multi-field data classes

2. Sum Types: Addition of Types

A sum type describes a value that can belong to one of several alternative types.

|A + B| = |A| + |B|

For example:

type Result =
  | { type: "success"; data: string }
  | { type: "failure"; error: Error };

Result represents two possibilities:

  • A success result.
  • A failure result.

A Result value can correspond to only one of these branches.

Structurally:

Result
├── Success
│   └── data: string
└── Failure
    └── error: Error

Common sum types include:

  • Enum variants
  • Tagged union
  • Discriminated union
  • Rust's enum
  • Haskell's algebraic data constructors

Note that a concrete implementation of a sum type may involve tags, discriminant fields or runtime type information, but these implementation details do not change its type-composition semantics.

3. Unit Types: Types with Only One Value

A unit type is a type with exactly one possible value.

For example:

  • Rust: ()
  • Haskell: ()
  • Kotlin: Unit

Its cardinality is:

|1| = 1

Unit types are often used to represent branches that carry no additional data.

For example:

enum Status {
    Loading,
    Success(String),
    Failure(String),
}

Here Loading can be understood as a constructor branch that carries no extra fields.

Algebraically, it is like a branch containing only the unit value.

4. Empty Types: Types with No Values

An empty type has no legal values, and its cardinality is:

|0| = 0

In Rust, ! is the never type, denoting a type that never produces a value normally.

fn terminate() -> ! {
    panic!("程序终止");
}

Empty types are significant in type theory:

  • No value of one can be constructed normally.
  • They can be used to represent states that cannot occur.
  • They can be used to describe functions that do not return.
  • In some type operations they act as the zero element of sum types.

It is important to distinguish: different languages may define the empty type, bottom type (Bottom Type), and Never Type differently; they cannot simply be assumed to be completely equivalent across all languages.

III. Product Type

A product type is a combination of multiple fields, all of which together form a complete value.

1. Basic Structure

type Point = {
  x: number;
  y: number;
};

A Point simultaneously contains two coordinate fields.

Its type structure can be represented as:

Point = Number \times Number

A Point value must satisfy the structural requirements of both fields.

2. Tuple Type

Tuples are also a typical product type.

type UserInfo = [string, number, boolean];

const user: UserInfo = ["Alice", 25, true];

It consists of three elements whose positions are fixed and whose types can differ.

Differences between tuples and ordinary arrays:

Comparison Dimension Tuple Array
Number of elements Usually fixed or constrained by the type Usually variable
Element types Can differ by position Usually share the same element type
Access method Accessed by fixed position Accessed by index
Type expression Combination of multiple fields Collection of elements of the same type

3. Combining Product Types

Product types can be nested:

type Address = {
  city: string;
  street: string;
};

type User = {
  name: string;
  age: number;
  address: Address;
};

Its structure can be understood as:

User = String \times Number \times Address

Expanding further:

User = String \times Number \times (String \times String)

Product types are associative:

(A \times B) \times C \cong A \times (B \times C)

Here, \cong denotes structural isomorphism; it does not mean that the concrete type declarations in different languages are necessarily exactly the same.

4. Engineering Significance of Product Types

Product types are suitable for expressing data constraints that must all hold simultaneously.

Typical scenarios:

  • User information.
  • Database records.
  • Configuration objects.
  • Network request parameters.
  • Business entities.
  • Multiple input parameters of a function.

They can combine multiple related fields into a single whole with a clear structure.

IV. Sum Type

A sum type means that a value can be selected from only one of multiple candidate branches.

It emphasizes “multiple possible states” rather than the simultaneous existence of multiple fields.

1. Basic Structure

For example, a payment method can be a bank card, Alipay, or WeChat Pay:

type PaymentMethod =
  | { type: "card"; cardNumber: string }
  | { type: "alipay"; account: string }
  | { type: "wechat"; openId: string };

A PaymentMethod value can belong to only one of these branches.

Its algebraic expression is:

PaymentMethod = Card + Alipay + Wechat

Each branch can itself also be a product type.

Therefore, sum types can combine product types to construct more complex data structures.

2. Tagged Union: A Sum Type with Tags

In engineering practice, sum types are often implemented using a tag field.

type Shape =
  | {
      kind: "circle";
      radius: number;
    }
  | {
      kind: "rectangle";
      width: number;
      height: number;
    };

Here:

  • kind identifies the current branch.
  • radius belongs only to the circle branch.
  • width and height belong only to the rectangle branch.

kind is the discriminant field (Discriminant).

Using a discriminant field allows the compiler to identify which branch the current value belongs to and to narrow the type within that branch.

function getArea(shape: Shape): number {
  switch (shape.kind) {
    case "circle":
      return Math.PI * shape.radius ** 2;

    case "rectangle":
      return shape.width * shape.height;
  }
}

Type narrowing here relies on TypeScript's control flow analysis.

If a triangle branch is added, strict exhaustiveness checking can help detect cases that have not yet been handled.

3. Sum Types in Rust

Rust uses enum to express sum types with data:

enum Message {
    Quit,
    Move { x: i32, y: i32 },
    Write(String),
    ChangeColor(u8, u8, u8),
}

Message contains four possible messages:

  • Quit: carries no data.
  • Move: carries two coordinate fields.
  • Write: carries a string.
  • ChangeColor: carries three color components.

Each enum value corresponds to exactly one variant.

Rust's enum is not just an enum in the traditional sense that stores only integer constants; it can carry data with different structures and is an important tool for expressing sum types.

4. Engineering Significance of Sum Types

Sum types are suitable for expressing mutually exclusive states or a finite set of branches.

Typical scenarios:

  • A request succeeds or fails.
  • A user is logged in or not logged in.
  • Payment method selection.
  • Order status.
  • Message type.
  • Syntax tree node.
  • Business operation result.

Sum types can explicitly encode the state space into the type system, reducing the space of representable illegal states.

V. Combining Product Types and Sum Types

The most important capability of ADTs is the nested composition of product types and sum types.

For example, a network request result:

type ApiResult =
  | {
      status: "success";
      data: {
        id: number;
        name: string;
      };
    }
  | {
      status: "failure";
      error: {
        code: number;
        message: string;
      };
    };

This type uses two structures at the same time:

  • The outermost layer is a sum type: success or failure.
  • Inside each branch is a product type: the status field and the corresponding data field exist at the same time.

Algebraic expression:

ApiResult = (Success \times UserData) + (Failure \times ErrorData)

Further expanded:

ApiResult = (String \times UserData) + (String \times ErrorData)

The expressions here are structural illustrations; the labels in actual types are usually finite literal types.

1. Composition Structure of ADTs

flowchart TB
    A["Algebraic Data Type ADT"] --> B["Product Type"]
    A --> C["Sum Type"]

    B --> D["Multiple fields exist simultaneously"]
    B --> E["Struct / Record / Tuple"]

    C --> F["Choose one of multiple branches"]
    C --> G["Enum / Tagged Union"]

    D --> H["Compose complex data structures"]
    F --> H
    H --> I["Nested ADT"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style I fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

2. Modeling Business States with ADTs

Take an order as an example:

type Order =
  | {
      status: "pending";
      createdAt: Date;
    }
  | {
      status: "paid";
      paidAt: Date;
      transactionId: string;
    }
  | {
      status: "shipped";
      paidAt: Date;
      shippedAt: Date;
      trackingNumber: string;
    }
  | {
      status: "cancelled";
      reason: string;
    };

A traditional design might use an object containing many optional fields:

type WeakOrder = {
  status: string;
  createdAt?: Date;
  paidAt?: Date;
  shippedAt?: Date;
  transactionId?: string;
  trackingNumber?: string;
  reason?: string;
};

The second design has a large space of invalid states:

  • The order status is paid, but there is no payment time.
  • The order status is shipped, but there is no tracking number.
  • The order status is cancelled, yet it contains unrelated payment fields.
  • The status string may contain typos or unknown values.

ADTs place the data required by each state into its own branch, keeping the data structure consistent with the business state.

This does not mean that all business constraints can be automatically guaranteed by the type system. For example, temporal ordering, amount validity, permission constraints, and so on still require business validation.

6. ADTs and Pattern Matching

Pattern matching is one of the most important ways to use ADTs.

It allows a program to execute different logic according to the data structure and specific branch.

1. Basic Pattern Matching

Rust example:

enum Result<T, E> {
    Ok(T),
    Err(E),
}

fn handle_result(result: Result<i32, String>) {
    match result {
        Result::Ok(value) => {
            println!("成功:{}", value);
        }
        Result::Err(error) => {
            println!("失败:{}", error);
        }
    }
}

match matches the current value against enum variants.

After a successful match, you can also extract the data carried by the branch.

2. Exhaustiveness Checking

A key feature of pattern matching is exhaustiveness checking.

Suppose a type has three branches:

enum Status {
    Pending,
    Success,
    Failed,
}

If only two branches are handled:

fn process(status: Status) {
    match status {
        Status::Pending => println!("等待"),
        Status::Success => println!("成功"),
    }
}

The Rust compiler will report that the Failed branch is not covered.

Exhaustiveness checking helps developers find missing state-handling logic.

Its important value is that when a new branch is added to a type, the relevant pattern-matching code can expose the places that need modification at compile time.

3. Exhaustiveness Checking and Default Branches

Some languages allow default branches:

function handleStatus(status: string) {
  switch (status) {
    case "pending":
      return "等待";

    case "success":
      return "成功";

    default:
      return "其他状态";
  }
}

A default branch can handle unknown values, but it may mask the problem that newly added branches are not explicitly handled.

For finite and controlled business states, exhaustiveness checking is usually more appropriate.

TypeScript can achieve this with never:

type Status =
  | "pending"
  | "success"
  | "failed";

function assertNever(value: never): never {
  throw new Error(`Unexpected value: ${value}`);
}

function handleStatus(status: Status): string {
  switch (status) {
    case "pending":
      return "等待";

    case "success":
      return "成功";

    case "failed":
      return "失败";

    default:
      return assertNever(status);
  }
}

When a new branch is added to Status and the switch does not handle it, status can no longer be narrowed to never, thereby triggering a type error.

Note that TypeScript's type checking mainly occurs at compile time; external input at runtime still needs to be validated.

VII. ADTs and Implementations in Common Languages

Different languages use different syntax and implementation approaches to express ADTs.

Language Product Type Sum Type Typical Mechanism
Haskell Record, Tuple data with multiple constructors Native support for algebraic data types
Rust Struct, Tuple Struct Enum Enum variants carry data
TypeScript Object, Tuple Union Type Union types and discriminant fields
Kotlin Data Class Sealed Class / Sealed Interface Sealed hierarchy
Swift Struct, Tuple Enum Enum associated values
OCaml Record, Tuple Variant Variant types
Scala Case Class Sealed Trait / Enum Sealed type hierarchy
C Struct Tagged Union (manual implementation) Structs, unions, and tags