Functional programming: Algebraic data types

Based on this Wikipedia article.

Composite data types

Composite (or compound) data types consist of a few primitive data types or other composite types. Examples of composite data types are C/C++ structure and union.

Product data type

Let’s look at the C/C++ structure example:

struct account {
   int account_number;
   char *first_name;
   char *last_name;
   float balance;
};

This type contains account_number AND first_name AND last_name AND balance fields – the AND makes it a product type, where product is boolean AND.

Sum data type

Let’s now look at the following example of C/C++ union:

union number {
  int8_t i8;
  int16_t i16;
  int32_t i32;
  int64_t i64;
  float f32;
  double f64;
};

This type can accommodate an int8_t OR int16_t OR int32_t OR int64_t OR float OR double number – the OR makes the type a kind of sum type (not quite yet), where sum is boolean OR.

This is not the whole of the sum data type yet. The actual type of the data currently stored in a C/C++ union is only known at run time, and the program that uses the union should be able to handle that at run time.

The union can be extended to tagged union, which may look like this:

struct number {
  uint8_t tag;
  union {
    int8_t i8;
    int16_t i16;
    int32_t i32;
    int64_t i64;
    float f32;
    double f64;
  } value;
}

The tag specifies the type of the value at run time.

Such tagged union type is called sum data type.

Hybrid data types

Product and sum data types are the base algebraic data types. The data types composed of product and sum data types are called hybrid data types.

It probably makes not that much sense to use the struct number type for the balance field in the struct account, but here it is – a hybrid data type example:

struct account {
int account_number;
char *first_name;
char *last_name;
struct number balance;
};

Algebraic data types

The product, sum and hybrid data types are what is called algebraic data types.

See also

Functional Programming: Terminology