Declare User-defined Types with Algebraic Datatypes

There are two main ways to construct compound datatypes:

• Combination: We define a complex datatype by combining other types. For instance, the pair type int * string consists of all combinations whose first component is an integer and a string. This kind of type is also called a product type because it resembles the Catesian product.

• Alternation: We define a type as a set of alternatives. For example, the list data type is represented by two alternatives. One alternative is [], the other is a pair —a combination itself— containing the head and the tail. A type defined this way is also known as sum type. This type is the sum of all alternatives.

Algebraic data types provide a universal mechanism to define structured data by blending the power of both combination and alternation. The term algebraic comes from the properties that an algebraic datatype is created from—sum and product.

Example—modeling geometric shapes

Suppose we want to model geometric shapes. For the sake of simplicity, we consider two kinds of shapes—circle and rectangle. Moreover, a circle is associated with a radius, while a rectangle has a width and length. We can represent shape as an algebraic data type as follows.

type shape =  Circle of float
              | Rectangle of float * float

The two kinds of shapes are represented by two different data constructors, Circle and Rectangle separated by the bar symbol |. Furthermore, the Circle constructor carries the circle’s radius as a float, whereas Rectangle requires two floats denoting the rectangle’s width and height.

With this definition, we can use the constructors to create shape values. For example, we can create several shapes and store them in a list.

[Circle 2.; Circle 3.; Rectangle (1., 2.)]

Moreover, an algebraic data type can be defined in terms of itself, making it ideal for modeling a recursive structure. For instance, we may add a new ComplexShape constructor that represents a shape composed of other shapes.

type shape =  Circle of float
              | Rectangle of float * float
              | ComplexShape of shape list

This algebraic datatype is recursive because the ComplexShape constructor refers to shape in its definition.

For example, with this definition, we can define a complex shape consisting of three other shapes—circle, rectangle, and another complex shape.

ComplexShape [Circle 1.; Rectangle (2., 3.); ComplexShape [Circle 4.; Circle 5.]

Like tuples and lists, we use pattern matching to deconstruct a value of an algebraic datatype into its various cases. For instance, let’s write a function, area: shape -> float, to calculate the area of a shape.