In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
, a generalized algebraic data type (GADT, also first-class phantom type, guarded recursive datatype, or equality-qualified type) is a generalization of the algebraic data type
Algebraic data type
In computer programming, particularly functional programming and type theory, an algebraic data type is a datatype each of whose values is data from other datatypes wrapped in one of the constructors of the datatype. Any wrapped datum is an argument to the constructor...
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
ML is a general-purpose functional programming language developed by Robin Milner and others in the early 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM...
, applying to parametric types.
With this extension, the parameters of the return type
Data type
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
of a data constructor can be freely chosen when declaring the constructor, while for algebraic data types in Haskell 98, the type parameter of the return value is inferred from data types of parameters; they are currently implemented in the GHC
Glasgow Haskell Compiler
The Glorious Glasgow Haskell Compilation System, more commonly known as the Glasgow Haskell Compiler or GHC, is an open source native code compiler for the functional programming language Haskell. The lead developers are Simon Peyton Jones and Simon Marlow...
compiler as a non-standard extension, used by, among others, Pugs
Pugs
Pugs is a compiler and interpreter for the Perl 6 programming language, started on February 1, 2005 by Audrey Tang.Pugs development is now placed on hiatus, with most Perl 6 implementation efforts now taking place on Rakudo; however, its source repository is still used for storing the official Perl...
Darcs is a distributed revision control system created by David Roundy; it was designed to replace traditional, centralized source control systems such as CVS and Subversion...
. The Omega programming language extends Haskell with generalized algebraic data types.
History
An early version of generalized algebraic data types where given in and based on pattern matching in ALF.
Generalized algebraic data types where introduced independently by and prior by as extensions to ML's and Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
In computer programming, particularly functional programming and type theory, an algebraic data type is a datatype each of whose values is data from other datatypes wrapped in one of the constructors of the datatype. Any wrapped datum is an argument to the constructor...
s. Both are essentially equivalent to each other. They are similar to the inductive families of data types (or inductive datatypes) found in Coq
Coq
In computer science, Coq is an interactive theorem prover. It allows the expression of mathematical assertions, mechanically checks proofs of these assertions, helps to find formal proofs, and extracts a certified program from the constructive proof of its formal specification...
The calculus of inductive constructions is the underlying core language of the Coq Proof Assistant. It is based on the calculus of constructions extended by inductive definitions as they are known from intuitionistic type theory....
and other dependently-typed languages, modulo the dependent types and except that the latter have an additional positivity restriction which is not enforced in GADTs.
introduced extended algebraic data types which combine GADTs together with the existential data types and type class
Type class
In computer science, a type class is a type system construct that supports ad-hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types...
Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction....
in the absence of any programmer supplied type annotations is undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
and functions defined over GADTs do not admit principal type
Principal type
In type theory, the principal type of an expression is the most general possible type given an expression. One way to compute the principal type of an expression is by deploying Robinson's unification algorithm, which is used by the Hindley–Milner type inference algorithm.Expressions always...
s in general. Type reconstruction requires several design trade-offs and is on-going research .
Features
Non-uniform return parameter type
Existentially quantified type parameters
Local constraints
In a broad definition, generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters...
In computer science, higher-order abstract syntax is a technique for the representation of abstract syntax trees for languages with variable binders.-Relation to first-order abstract syntax:...
Invariant and invariance may have several meanings, among which are:- Computer science :* Invariant , an Expression whose value doesn't change during program execution* A type in overriding that is neither covariant nor contravariant...
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s, expressing constraints in embedded domain-specific languages, and modelling objects.
In computer science, higher-order abstract syntax is a technique for the representation of abstract syntax trees for languages with variable binders.-Relation to first-order abstract syntax:...
in a type safe fashion. Here is an embedding of the simply-typed lambda calculus with an arbitrary collection of base types, tuples and a fixed point combinator
Fixed point combinator
In computer science, a fixed-point combinator is a higher-order function that computes a fixed point of other functions. A fixed point of a function f is a value x such that x = f. For example, 0 and 1 are fixed points of the function f = x2, because 0 = 02 and 1 = 12...
:
data Lam :: * -> * where
Lift :: a -> Lam a
Tup :: Lam a -> Lam b -> Lam (a, b)
Lam :: (Lam a -> Lam b) -> Lam (a -> b)
App :: Lam (a -> b) -> Lam a -> Lam b
Fix :: (Lam a -> Lam a) -> Lam a
And a type safe evaluation function:
eval :: Lam t -> t
eval (Lift v) = v
eval (Tup e1 e2) = (eval e1, eval e2)
eval (Lam f) = \x -> eval (f (Lift x))
eval (App e1 e2) = (eval e1) (eval e2)
eval (Fix f) = eval (f (Fix a))
We would have run into problems 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 we would still be restricted to a single base type. Furthermore, 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.
Further reading
Applications|ref=harv}}
Semantics
Patricia Johann and Neil Ghani (2008). "Foundations for Structured Programming with GADTs".
Arie Middelkoop, Atze Dijkstra and S. Doaitse Swierstra (2011). "A lean specification for GADTs: system F with first-class equality proofs". Higher-Order and Symbolic Computation.
A wiki is a website that allows the creation and editing of any number of interlinked web pages via a web browser using a simplified markup language or a WYSIWYG text editor. Wikis are typically powered by wiki software and are often used collaboratively by multiple users. Examples include...
Simon Peyton Jones is a British computer scientist who researches the implementation and applications of functional programming languages, particularly lazy functional languages...
Simon Peyton Jones is a British computer scientist who researches the implementation and applications of functional programming languages, particularly lazy functional languages...
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
