Generalized algebraic data type
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In functional programming, a generalized algebraic data type (GADT, also first-class phantom type, guarded recursive datatype, or equality-qualified type ) is a generalization of a parametric algebraic data type (ADT).
In functional programming, a generalized algebraic data type (GADT, also first-class phantom type, guarded recursive datatype, or equality-qualified type ) is a generalization of a parametric algebraic data type (ADT). -- A parametric ADT that is not a GADT data List a = Nil | Cons a (List a) integers :: List Int integers = Cons 12 (Cons 107 Nil) strings :: List String strings = Cons "boat" (Cons "dock" Nil) -- A GADT data Expr a where EBool :: Bool -> Expr Bool EInt :: Int -> Expr Int EEqual :: Expr Int -> Expr Int -> Expr Bool eval :: Expr a -> a eval e = case e of EBool a -> a EInt a -> a EEqual a b -> (eval a) == (eval b) expr1 :: Expr Bool expr1 = EEqual (EInt 2) (EInt 3) ret = eval expr1 -- False They are currently implemented in the Glasgow Haskell Compiler (GHC) as a non-standard extension, used by, among others, Pugs and Darcs.
OCaml supports GADT natively since version 4.00.
The GHC implementation provides support for existentially quantified type parameters and for local constraints. data Lam :: * -> * where Lift :: a -> Lam a -- ^ lifted value Pair :: Lam a -> Lam b -> Lam (a, b) -- ^ product Lam :: (Lam a -> Lam b) -> Lam (a -> b) -- ^ lambda abstraction App :: Lam (a -> b) -> Lam a -> Lam b -- ^ function application Fix :: Lam (a -> a) -> Lam a -- ^ fixed point And a type safe evaluation function: eval :: Lam t -> t eval (Lift v) = v eval (Pair l r) = (eval l, eval r) eval (Lam f) = \x -> eval (f (Lift x)) eval (App f x) = (eval f) (eval x) eval (Fix f) = (eval f) (eval (Fix f)) The factorial function can now be written as: fact = Fix (Lam (\f -> Lam (\y -> Lift (if eval y == 0 then 1 else eval y * (eval f) (eval y - 1))))) eval(fact)(10) Problems would have occurred using regular algebraic data types.
Dropping the type parameter would have made the lifted base types existentially quantified, making it impossible to write the evaluator. With a type parameter, it is still restricted to one base type. Further, ill-formed expressions such as App (Lam (\x -> Lam (\y -> App x y))) (Lift True) would have been possible to construct, while they are type incorrect using the GADT. A well-formed analogue is App (Lam (\x -> Lam (\y -> App x y))) (Lift (\z -> True)) .
This is because the type of x is Lam (a -> b) , inferred from the type of the Lam data constructor.
See also
Type variable
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373761604 under CC BY-SA 4.0; modifications have been made.