Agdatypes

Agdatypes are the data types defined within the Agda programming language, a dependently typed functional language used for programming and formal verification. The term combines the name Agda with data types and is often used to refer to algebraic data types defined in Agda, including more expressive dependent variants known as inductive families.

Agda supports declaring data types with constructors that build values in a type-safe way. A defining feature is the use of dependent types, where the type may depend on a value. This enables the encoding of invariants directly in the type system. Agdatypes can be parameterized by type variables and, in the dependent setting, by values, allowing a single type to represent a family of related structures.

Common examples of Agdatypes include natural numbers, lists, and vectors. For instance, a simple natural number type can be declared with a base case zero and a successor constructor. A parametric list type is defined by a type parameter A and includes nil and cons constructors. A dependent example is Vector, a list-like type indexed by a length, so that operations can carry length information in their types.

Pattern matching is used to define functions on Agdatypes, and recursion must satisfy the language’s termination checks to ensure totality. This combination supports both executable code and formal reasoning about programs, making Agdatypes central to proofs and verified software inside Agda.

Historically, Agda and its type system emerged to support constructive mathematics and formal verification, with Agdatypes playing a core role in representing data, invariants, and proofs within a single formal framework. See also dependent types, inductive families, Agda, and type theory.