Building New Types

Base types vs compound types

In any language there are based types, such as int, bool, unit, char. We can then use these in nested compound types, such as tuples, lists, and options.

For any programming language, there are 3 fundamental type building-blocks:

• “Each of”: a t value contains values of each of t1 t2 ... tn
  • The entire idea is to build a new tyoe t where the values of t have each of some other collection of types.
• “Self Reference”: a t value can refer to other t values
  • with each of and one of we cannot build types like lists, since those are recursive as each value contains a list that is smaller.
• “One of”: a t value contains values of one of t1 t2 ... tn
  • A value contains one of the values from a collection of distinct types

Examples

• Tuples build each-of types
  • int * bool contains an int and a bool
• Option build one-of types
  • int option contains an int or it contains no data
• Lists use all three building blocks
  • int list contains an int and another int list or it contains no data

Note how each of the building blocks can be associated with and, or, or recursion.

Records