3.6 User-defined Types

A type is a set of values. Some common types, presented in Section 3.3, are built into the language and the programmer does not declare them. All other types used in a program must be declared by the programmer. The classification of some types as builtin vs. user-defined is only a matter of convenience. Builtin and user-defined types are conceptually very similar. In fact, the declaration of some builtin types could have been left to the programmer. For example:

is exactly how the builtin “Boolean” type would be declared if it were not builtin. In this declaration, the identifier “Boolean” is referred to as a type constructor, whereas the identifiers “False” and “True” are referred to as data constructors. The following declarations, very similar to the previous one, define plausible types “WeekDay” and “PrimaryColor”.

All these types are finite, i.e., they define a finite set of values, and resemble enumerated types in the Pascal or C languages.

The declaration of an infinite type is similar, but as one should expect, must be (directly or indirectly) recursive. The following declaration defines a binary tree of integers. We recall that the typical definition of this type says that a binary tree is either a leaf or it is a branch consisting of two binary trees. Not surprisingly, this definition is recursive which accounts for an infinity of trees. The words “leaf” and “branch” are conventional names used to distinguish the two kinds of trees and have no other implicit meaning. Often, branches include a decoration, a value of some other arbitrary type. If a tree $T$ is a branch, the two trees in the branch are referred to as the left and right children of $T$. A declaration defining binary trees where the decoration is an integer follows:

All the following expressions are values of type “IntTree”:

The first tree is a leaf and therefore it contains no decoration. The second tree contains a single decoration, “0”, and two children both of which are leaves. The third tree contains three decorations. Binary trees are interesting because many efficient searching and sorting algorithms are based on them.

User-defined types can be parameterized by means of other types similar to the builtin type list introduced in Section 3.3. These types are called polymorphic. For example, if the type of the decoration of a binary tree is made a parameter of the type of the tree, the result is a polymorphic binary tree. This is achieved by the following declaration [Browse Program][Download Program]:

The identifier “a” is a type variable. Observe that the type variable not only defines the type of the decoration, but also the type of the subtrees occurring in a branch. In other words, the type that parameterizes a tree also parameterizes the children of a tree. The type variable can be implicitly or explicitly bound to some type, e.g., “Int” or “WeekDay” defined earlier. For example, a function that looks for the string “Curry” in a tree of strings is defined as [Browse Program][Download Program]:

The type of the argument of function “findCurry” is “BinTree String”. The binding of type “String” to the type variable of the definition of the polymorphic type “BinTree” is automatically inferred from the definition of function “findCurry”.

A polymorphic type such as “BinTree” can be specialized by binding its variable to a specific type by an explicit declaration as follows [Browse Program][Download Program]:

where “type” is a reserved word of the language. This declaration defines “IntTree” as a synonym of “BinTree Int”. The synonym can be used in type declarations to improve readability. The following example defines a function that tallies all the decorations of a tree of integers [Browse Program][Download Program]: