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)
References in periodicals archive ?
The new types include recursive type variables, ranged over by [Alpha], and the recursive types themselves, [micro][Alpha].
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.
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.
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.
This analogy can be made deeper, by noting that there are now several semantics for objects that use existential types, and usually recursive types, to define object types [Bruce 1994; Pierce and Turner 1994; Abadi and Cardelli 1996].
The new type system contains both recursive types and an unusual notion of subtyping.
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.