Algebraic Data Type
Subject: Computer and Technology noun /ˌæl.dʒəˈbreɪ.ɪk ˈdeɪ.tə ˌtaɪp/ 1 definition
- type-systems
- functional-programming
- programming-languages
- computer-science
-
Definition (noun)
Entry #264 · UpdatedAn Algebraic Data Type (ADT) is a composite type constructed by combining other types through two fundamental operations: products, which group multiple values together, and sums, which represent an exclusive choice among distinct tagged variants. Its name reflects type algebra, where the number of possible values of a product type equals the product of its component cardinalities and that of a sum type equals their sum. Languages with first-class ADTs pair them with structural pattern matching and compile-time exhaustiveness checks, allowing code to destructure nested data while guaranteeing that every valid variant is explicitly handled. Unlike open object-oriented inheritance hierarchies or untagged C-style unions, an ADT defines a closed, discriminated set of shapes—trading open extensibility of new variants for strong static invariants that make invalid domain states unrepresentable.
Common Forms
Product Types: Group multiple constituent fields together—such as tuples, records, or structs—so that every instance simultaneously holds one value for each member type.
Sum Types (Tagged Unions): Represent a value taking exactly one of several named variants—such as Rust
enumdeclarations, Haskelldataconstructors, or TypeScript discriminated unions—each carrying a distinct tag and optional payload.Recursive Algebraic Data Types: Reference the type being defined inside one or more of its own variants to model inductive structures such as linked lists, binary trees, and abstract syntax trees (ASTs).
Generalized Algebraic Data Types (GADTs): Extend standard ADTs by allowing individual constructors to refine the parent type's type parameters, enabling type-safe evaluators and embedded domain-specific languages in languages like Haskell and OCaml.
Example
In Rust, an API client defines
enum FetchOutcome { Success { status: u16, body: Vec<u8> }, TimedOut, Rejected { status: u16, reason: String } }, pairing a sum type across three variants with product-type payloads insideSuccessandRejected. When a handler evaluates amatchexpression overFetchOutcome,rustcrefuses to compile if theTimedOutarm is omitted, guaranteeing every response state is explicitly handled.