GADTs

GADTs, or Generalized Algebraic Data Types, are a feature of some statically typed functional programming languages that extend the expressiveness of algebraic data types. In a standard algebraic data type, each constructor produces the same type. GADTs allow constructors to specify the exact result type, which may depend on the constructor. This enables more precise typing and can encode invariants directly in the type system.

In languages that support GADTs, type parameters can be refined by constructors. For example, in Haskell with the GADTs extension, one can write a data family where the return type of a constructor depends on the chosen constructor. A common illustration is an expression language where the type parameter tracks the evaluated type:

data Expr a where

I :: Int -> Expr Int

B :: Bool -> Expr Bool

Add :: Expr Int -> Expr Int -> Expr Int

IsZero :: Expr Int -> Expr Bool

Here, the type parameter a of Expr a is refined by the constructor, so pattern matching can reveal more precise information about the result type.

Benefits include encoding invariants such as well-typed abstract syntax trees, safe interpreters, and typed stages of computation. GADTs interact with type inference and often require explicit type annotations or language extensions to use effectively.

Limitations involve increased type signatures and potential complexity in type checking and inference. They may also complicate code readability and maintenance. GADTs are implemented in several languages, notably Haskell and some ML-family languages, each with its own syntax and rules.

See also: dependent types, type families, indexed types, type safety.