recursive type

Also found in: Wikipedia.

recursive type

A data type which contains itself. The commonest example is the list type, in Haskell:

data List a = Nil | Cons a (List a)

which says a list of a's is either an empty list or a cons cell containing an 'a' (the "head" of the list) and another list (the "tail").

Recursion is not allowed in Miranda or Haskell synonym types, so the following Haskell types are illegal:

type Bad = (Int, Bad) type Evil = Bool -> Evil

whereas the seeminly equivalent algebraic data types are acceptable:

data Good = Pair Int Good data Fine = Fun (Bool->Fine)
This article is provided by FOLDOC - Free Online Dictionary of Computing (
References in periodicals archive ?
The new types include recursive type variables, ranged over by [Alpha], and the recursive types themselves, [micro][Alpha].[Tau].
It is similar to rule [9] used for embedded functions in that the outer agent may have different information about the nature of the recursive type. For instance, the outer agent may know that the value is of type [micro][Alpha].1 + t x [Alpha], the type of t-lists, whereas the inner agent, for whom [[Delta].sub.j](t) = int views the value as an int-list.(7) The side condition on [[micro]4] ensures that the dynamic semantics are deterministic--rule [7] applies to a disjoint collection of terms.
Recursive datatypes such as intlist above naturally lead to recursive type expressions.
This is not acceptable, so we extend our type system with recursive type expressions, that is, type expressions that are infinite but regular.
Automating recursive type definitions in higher order logic.
The recursive type (rec ([Y1 (+ nil (cons X1 Y1))]) Y1) denotes proper lists containing elements of type X1.
The following procedure from the introduction illustrates a presentation type that involves a union type, a recursive type, place holders, and a shared type variable:
A second cause of schema incorrectness is due to the presence of structurally recursive types that, when defined within certain hierarchical patterns, cause the nontermination of the inheritance process.
Additional Key Words and Phrases: Databases, graph theory, inheritance conflicts, inheritance process, object-oriented database schemas, recursive types
It is important to realize that safe dynamics are not simply the combination of partial dynamics with recursive types. A key in our approach is the use of recursion at the kind level.
Heintze asserted in 1995 that a program can be safety checked with an equality-based control-flow analysis if and only if it can be typed with recursive types. In this article we falsify Heintze's assertion, and we present a type system equivalent to equality-based control-flow analysis.
For our programming language we take an explicitly typed lambda calculus extended with products, sums, and recursive types and equipped with a conditional and a fixed-point operator.