gadt

GADT stands for Generalized Algebraic Data Type, a form of algebraic data type used in statically typed functional programming languages. Unlike conventional algebraic data types (ADTs), GADTs allow the result type of each data constructor to be instantiated to more specific type instances, effectively giving constructors their own return types. This yields type indices and more precise typing information that the compiler can use during pattern matching and type checking.

GADTs are useful for encoding invariants in types, representing typed abstract syntax trees, implementing safe heterogeneous containers, and modeling state transitions where the type carries protocol or state information. They enable programs to express richer relationships between values at the type level, often reducing the need for runtime checks and improving safety.

Semantically, GADTs generalize ADTs and are closely related to indexed or dependent types; they can be viewed as a limited form of dependent typing. Their increased expressiveness complicates type inference, so many implementations require explicit type annotations or language extensions. Popular functional languages that support GADTs include Haskell (via the GADTs extension) and OCaml (with built-in support for generalized variants).

While powerful, GADTs introduce complexity in type checking, may interact subtly with features like type classes or polymorphism, and can make code harder to read if overused. They remain a widely adopted tool for writing safer, more expressive typed programs.