Algebraic data types

1 Overview of Algebraic Data Types

1.1 Core idea: building types from constructors

Algebraic data types (ADTs) define composite data by specifying two ingredients: constructors that create values, and type expressions that describe how those values are assembled. The defining feature is that the shape of a value is reflected directly in the type. This lets programmers describe structured data—such as trees, expressions, or configuration records—using smaller building blocks like integers and other simple types.

1.2 Product types vs. sum types

ADTs organize composite types using two dual forms. Product types combine component types into a single structure, corresponding to “multiplication” in type algebra. Sum types provide alternatives among component types, corresponding to “addition” in type algebra. Any richer data shape can typically be expressed using some combination of products and sums, often with recursion for repeating structure.

1.3 Constructors, fields, and tagging

Product types are introduced by constructors that specify multiple fields (or components) of potentially different types. Sum types use constructors that tag which alternative is present and carry the associated data for that alternative. Tagging matters because it distinguishes values that are superficially similar but belong to different alternatives, enabling safe pattern matching and clear invariants.

1.4 Recursion and inductive structure

Many real data structures are recursively defined, such as lists and syntax trees. ADTs express recursion by allowing a constructor to refer to the ADT being defined. This yields inductive structure: values are built from base cases using constructors repeatedly, and each decomposition step reduces the “size” of the data in a well-founded manner, which is the intuition behind safe structural reasoning.

2 Product Types (Algebraic “Multiplication”)

2.1 Tuples and records as product types

A tuple is the simplest product type: it holds one value for each component type. Records extend this idea with named fields, improving readability and maintainability. In both cases, the value of a product type can be understood as having multiple parts that travel together under a single type.

2.2 Pairing semantics and projections

Product values support projection: retrieving each component in a typed way. For tuples, projections correspond to selecting component positions; for records, they correspond to selecting named fields. This yields a predictable interface: a product can be created by pairing components and later inspected by decomposing it along the same structure.

2.3 Optional/nullable fields as product extensions

Optionality is often modeled as an additional sum, but product-based modeling can also represent partial presence by embedding option-like components as fields. For example, a “profile” record might contain a component for a middle name that is allowed to be absent. This keeps the overall type a product of fields while allowing some fields to carry “maybe” semantics.

2.4 Nested products and associativity

Real-world types often nest product structures. A nested pair can usually be reorganized into a flattened tuple shape, and the idea of associativity captures that these reorganizations preserve informational content. While concrete syntax may differ, ADT reasoning treats them as structurally equivalent up to consistent rearrangement.

3 Sum Types (Algebraic “Addition”)

3.1 Tagged unions / variants

A sum type represents a choice among alternatives. Each alternative is introduced by a constructor that carries its own payload. The tag ensures that when a value is inspected, the program knows which constructor produced it, so it can safely access the associated data with the correct type.

3.2 Alternatives and pattern matching

Pattern matching on a sum type branches based on the tag and binds any payload variables. This style supports direct, readable handling of each alternative without manual checking logic. Because the alternatives are enumerated in the type definition, matching can be organized to mirror the conceptual cases in the domain model.

3.3 Empty and unit sum/product cases

Two boundary cases often appear in ADT algebra. An empty sum represents a type with no values; it is useful for expressing unreachable code paths or impossible states. A unit sum (sometimes paired with a unit product) represents a type with exactly one value, which is helpful when a constructor carries no meaningful data but still participates in a larger structure.

3.4 Combining multiple sum branches

Sum types can be expanded by adding more alternatives, yielding multiple branches. They can also be layered: a larger sum may contain variants whose payloads themselves include other sums. This composes the expressive power of ADTs, allowing complex “either/or” logic to be represented with explicit structure rather than implicit conventions.

4 Type Algebra and Isomorphisms

4.1 Representing type expressions as algebra

ADTs can be treated as algebraic expressions built from base types using product and sum operators. In this view, types correspond to expressions whose structure describes how values are formed and dismantled. The constructors then become the mechanisms that inhabit the expression, while pattern matching and projection correspond to deconstructing it.

4.2 Distributive-like relationships in ADTs

Type expressions often satisfy algebraic laws reminiscent of arithmetic. For instance, product distributes over sum in a way that can be mirrored by transforming ADTs: a value that is a product of a type with a sum of alternatives can be represented as a sum of products. The practical point is that multiple ADT shapes can encode the same information with different grouping.

4.3 Canonical forms and normalization intuition

Because ADT expressions can be rearranged, it is sometimes useful to talk about normal forms: a convention for how to group products and sums to make types easier to compare or reason about. Normalization does not necessarily change runtime representation in all systems, but it supports algebraic reasoning about equivalence and transformations.

4.4 Mapping between equivalent type shapes

When two type shapes are algebraically equivalent, there is often an isomorphism: a pair of functions that convert values back and forth without loss. In ADT terms, these conversions typically correspond to systematic re-grouping and re-tagging of constructors. Recognizing such equivalences helps in refactoring type definitions while preserving semantics.

5 Recursion and Inductive ADTs

5.1 Recursive type definitions

Recursive ADTs define self-referential structure using constructors that contain the ADT itself. For example, a tree node may contain subtrees of the same type. The key is that recursion must be mediated by constructors so that values remain finite and the type definition remains well-formed.

5.2 Base cases and structural decomposition

Inductive definitions include base cases—constructors that do not recurse. Together with recursive constructors, they ensure every value can be decomposed into a finite combination of base pieces. This decomposition is the foundation for writing total functions (those that handle all cases) and for reasoning about properties by induction on structure.

5.3 Recursive pattern matching strategies

When writing functions over recursive ADTs, pattern matching often separates base constructors from recursive ones. Recursive cases then process subcomponents, typically invoking the function recursively. This yields code that mirrors the inductive structure of the data, making both correctness arguments and maintenance easier.

5.4 Termination and well-founded structures (intuition)

Termination is tied to the idea that each recursive step reduces complexity—such as the depth of a tree or the remaining length of a list. While systems differ in how they enforce termination, the inductive nature of ADTs provides an intuition: recursion follows the shape of the data and therefore cannot proceed indefinitely if values are finite.

6 Common ADT Patterns

6.1 Lists, trees, and rose trees

List ADTs typically use a sum structure between an empty case and a non-empty case that carries a head element plus a recursive tail. Trees often use products and sums to represent branching, while rose trees generalize this by allowing nodes to have multiple children, usually expressed as a list of subtrees combined with node metadata.

6.2 Option/Maybe and result/either-like shapes

Option/Maybe-style types model the presence or absence of a value using a sum of “nothing” versus “just value.” Result/Either-like types model two outcomes, such as success versus failure, again using a tagged sum. These patterns avoid ambiguous sentinel values and encourage explicit case handling.

6.3 Enumerations as restricted sum types

Enumerations can be viewed as sum types with alternatives that carry no payload data. Even when an ADT case is “empty,” the constructor still provides a distinct tag. This yields strong typing: functions can distinguish among all enumerated cases without relying on ad hoc integer codes.

6.4 Expression ASTs (arithmetic terms, typed nodes)

Abstract syntax trees (ASTs) for expressions are classic ADT examples. Arithmetic terms can be modeled with sum types for operators and operands, combined with recursion to allow nested expressions. Typed nodes can further refine payloads, enabling the representation of well-formed expressions directly in the type system.

7 Pattern Matching and Exhaustiveness

7.1 Matching on product components

Pattern matching on product types typically binds each component in a single structured pattern. Because products contain fixed fields, matching does not require branching; it instead decomposes the value and assigns component variables with precise types. This makes product handling straightforward and predictable.

7.2 Matching on sum variants

Matching on sums branches by constructor. Each branch corresponds to one alternative and provides the payload bindings relevant to that alternative. This approach turns “runtime checks” into “compile-time structure,” since the set of cases comes from the type definition itself.

7.3 Exhaustiveness checking

Exhaustiveness checking verifies that all possible constructors of a sum type are covered by patterns. If a case is missing, the compiler can warn or reject the code depending on the language. This reduces the chance of unhandled scenarios and supports safer refactoring when ADTs evolve.

7.4 Refutable patterns and default handling

Not all patterns are equally strict. Some patterns may fail to match, especially in languages that allow pattern expressions with additional constraints. Default handling, such as a wildcard branch, can be used when the programmer intends to cover remaining cases uniformly, though exhaustive enumeration is often preferred for clarity and safety.

8 Operations on ADTs

8.1 Mapping (functor-like transformations)

Many ADTs support “mapping” operations that transform values inside a structure while preserving its outer shape. For example, a function that changes the element type of a recursive container can be implemented by applying a mapping step to each relevant payload position. This preserves structural metadata like length or tree branching.

8.2 Folding (catamorphisms) over recursive ADTs

Folding collapses a recursive ADT into a single result by replacing constructors with corresponding handler functions. In a fold, base cases and recursive cases are handled separately, and the fold guarantees that sub-results are combined systematically. This abstraction often yields concise, reusable traversals.

8.3 Unfolding (anamorphisms) and generation

Unfolding is the dual of folding: it builds an ADT from a seed value by repeatedly applying a generator that chooses constructors and produces next seeds. This is useful for generating structured data such as streams or trees from a description, while keeping the construction shape explicit in the type.

8.4 Zipping and combining structures

Zipping combines two structures of the same “shape” to produce a new structure. For product-like alignment, components combine positionally; for recursive structures, zipping often proceeds in parallel down the tree or list until termination conditions are reached. The type system can enforce that the shapes align before combining payloads.

9 Relationship to Type Classes and Generic Programming

9.1 Deriving common operations from ADT structure

Because ADTs expose a regular shape—constructors with fields and tags—many languages and libraries can derive common operations automatically. These include equality, string representation, serialization, and traversal utilities. Derivation reduces boilerplate while keeping behavior consistent across the codebase.

9.2 Reusability via traversal/fold abstractions

Generic traversal abstractions built around folding and mapping let programmers reuse logic. For instance, a function that collects all elements satisfying a predicate can be expressed as a fold, while mutation-free transformations can be expressed as maps or traversals. This encourages modularity: domain logic stays separate from structural plumbing.

9.3 Generic representations and constraints

Generic programming often represents ADT structure in a uniform representation so that generic functions can operate on many different ADTs. Constraints then express what is required for a generic operation—for example, that payload types support a specific method. The ADT’s constructor-and-field structure supplies the “schema” needed to guide such generic code.

9.4 Lawful behavior expectations (high-level)

When ADT-derived abstractions correspond to algebraic interfaces (such as functor- or monad-like behaviors in some ecosystems), libraries frequently expect certain laws. These are informal correctness conditions ensuring that the operations interact predictably with structure. While exact law sets vary by abstraction, the guiding idea is that behavior should be stable under composition and identity transformations.

10 Algebraic View of Data Modeling

10.1 Designing ADTs for clarity and safety

ADT design emphasizes explicit modeling of possible states and transitions through constructors and fields. When the type captures the intended invariants, functions become simpler and fewer invalid values can be constructed. The resulting code tends to read like a specification: the type lists the cases, and pattern matching expresses how each case is handled.

10.2 Avoiding invalid states by construction

A central advantage is that illegal combinations can be made unrepresentable. By choosing sum types for “either/or” distinctions and products for “both/and” requirements, programmers can prevent whole categories of errors. Instead of checking for invalid states at runtime, the design restricts what values exist in the first place.

10.3 Evolving ADTs without breaking invariants

ADTs may need extension over time, such as adding new constructors for additional scenarios. With exhaustiveness checking, many changes become compiler-visible: existing pattern matches can be updated systematically. This supports controlled evolution while keeping guarantees about handled cases.

10.4 Trade-offs: ergonomics vs. expressiveness

Expressive ADTs can increase type complexity, potentially making simple tasks more verbose. Conversely, highly structured types can also improve ergonomics by enabling safe automation and clearer reasoning. The trade-off typically depends on language features, tooling, and whether the benefits of explicit structure outweigh the added verbosity for the problem at hand.