Building Compound Types

• In any programming languages, there are 3 important “building blocks” for types:

1. Each-of types; a value of type t contains values whose types follow each oft1, t2, t3, …, tn (e.g. tuples, records)

   • Example: Tuples build each-of types.
     • A tuple with type int * bool contains each of the following:
       • int
       • bool
     • In other words, int * bool contains an int AND a bool
   • Records (will be covered later) also build each-of types.

2. One-of types; a value of type t contains values whose types follow one of t1, t2, t3, …, tn (e.g. enumerations, itemizations)

   • Example: Options build one-of types
     • Options are one of the following:
       • NONE
       • SOME e
     • For instance, an option with type int option either contains no data (NONE) OR some data (SOME int)

3. Self-reference (self-referential data types e.g. lists, trees)

   • Example: Lists is an each-of, one-of, and a self-referential type
     • A list xs is one of the following:
       • NONE
       • SOME (x :: xs)
     • The type of list xs is…
       • an each-of type because it contains an int and an int list
       • a one-of type because they contain either NONE or SOME (x :: xs).
       • a self-referential type because xs references itself in its type comment.

• In ML, we can build our own each-of and one-of types.

Records

<aside> 💽 Records are also called structures (…sound familiar?)

</aside>

• Records are a form of compound data that encapsulates multiple pieces of related data.

• They are identical to structures and bear some similarities to objects from OOP languages.

• Syntax: {f1 = v1, f2 = v2, f3 = v3, ... fn = vn}, where f1...fn are field names and v1...vn are values.

• Type-checking rules: {f1 : t1, f2 : t2, f3: t3, ... fn : tn}, where f1...fn are field names and t1...tn are the types of values v1...vn.