Chapter 4. Datatypes

Table of Contents
Matching Clauses and Case-Expressions
Enumerative Datatypes
Recursively Defined Datatypes
Exhaustiveness of Pattern-Matching
Example: Binary Search Tree
Example: Evaluating Integer Expressions

The feature of datatypes in ATS in largely taken from ML.

A datatype is like a tagged union type. For each datatype, there are some constructors associated with it, and these constructors are needed for constructing values of the datatype. As an example, the following syntax declares a datatype named intopt:

datatype intopt = | intopt_none of () | intopt_some of (int) // end of [intopt]

There are two constructors associated with intopt: intopt_none, which is nullary, and intopt_some, which is unary. For instance, intopt_none() and intopt_some(1) are two values of the type intopt. In order for accessing components in such values, a mechanism often referred to as pattern-matching is provided in ATS. I will demonstrate through examples that datatypes plus pattern matching can offer not only great convenience in programming but also clarity in code.

The code employed for illustration in this chapter plus some additional code for testing is available on-line.


Patterns in ATS can be defined inductively as follows:

Each variable can occur at most once in a given pattern, and this is referred as the linearity restriction on variables in patterns. For instance, (x, x) is not a legal pattern as the variable x appears twice in it. However, this restriction does not apply to the variable _, which represents the wildcard pattern.