In computer programming languages, a recursive type is a data type for values that may contain other values of the same type.

An example is the list type, in Haskell programming language:

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

This indicates that 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 programming language or Haskell synonym types, so the following Haskell types are illegal:

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

Conversely, the seemingly equivalent algebraic data types are acceptable:

data Good = Pair Int Good data Fine = Fun (Bool->Fine)

= See also =