## 1.8. Algebraic Data Types

An Orc datatype is an algebraic data type, or "tagged union". A datatype value contains a sequence of values enclosed by a tag. This value can be matched by a pattern.

Datatypes are defined by a `type` declaration. Each constructor in the declaration introduces a new tag, followed by a sequence of slots. The `|` separator allows multiple constructors to be defined at the same time.

In an untyped program, slots are written as `_`. In a typed program, slots contain types.

### 1.8.1. Syntax

  DeclareDatatype `::=` `type` TypeVariable TypeParameters? `=` Constructor `|` … `|` Constructor  Constructor `::=` Variable `(` Slot `,` … `,` Slot `)`  Slot `::=` Type ❙ `_`

### 1.8.2. Constructors

Each constructor is a site, which takes one argument for each slot of the constructor, and publishes a datatype value consisting of the sequence of argument values, tagged with that constructor's unique tag.

Each constructor also has a corresponding `unapply` member, which takes a value with that constructor's tag, removes the tag, and publishes the sequence of values as a tuple. If its argument does not have the tag, it halts. Thus, constructors can be used in pattern matching.

### 1.8.3. Type

A datatype declaration defines a new sum type.

Each constructor defined by the datatype has the function type `lambda` `[` `X0` `,``,` `Xn` `]``(` `T0` `,``,` `Tn` `)` `::` `S`, where `Xi` are the type parameters of the datatype, `Ti` are the types in the slots of the constructor, and `S` is the sum type.

Each constructor also has a corresponding `unapply` member, with type `lambda` `[` `X0` `,``,` `Xn` `]``(``S``)` `::` `(` `T0` `,``,` `Tn` `)`.

A datatype declaration may define a recursive type: the name of the type may be used in the definition of the type itself. In fact, this is the only way to declare a recursive type in Orc.

### 1.8.4. Examples

Enumeration
```{- An enumeration, such as Java's enum, can be represented by a datatype
whose constructors have no arguments. Note that an empty argument list,
(), is still needed.
-}
type objective = Primary() | Secondary() | Tertiary()

[Secondary(), Tertiary()]

{-
OUTPUT:
[Secondary(), Tertiary()]
-}
```
Geometric shape datatype
```{- A Shape type with three data constructors -}
type Shape = Rectangle(_, _) | Circle (_)

def area(Rectangle(width,height)) = width * height

area(Rectangle(2, 3)) | area(Circle(1))

{-
OUTPUT:PERMUTABLE:
6
3.1415926535897
-}
```
Binary tree node
```{- This is a binary tree datatype
Leaf nodes carry integer values
-}

type Node = LeafNode(Integer) | InnerNode(Node, Node)

{- Constructing a simple tree
/\
1 /\
2  3
-}
InnerNode(LeafNode(1),InnerNode(LeafNode(2),LeafNode(3)))

{-
OUTPUT:
InnerNode(LeafNode(1), InnerNode(LeafNode(2), LeafNode(3)))
-}
```
Polymorphic binary tree node
```{- This is a binary tree datatype
Leaf nodes carry values of type T
-}

type Node[T] = LeafNode(T) | InnerNode(Node[T], Node[T])

{- Constructing a simple tree
/\
"A" /\
"B"  "C"
-}
InnerNode[String](LeafNode("A"),InnerNode(LeafNode("B"),LeafNode("C")))

{-
OUTPUT:
InnerNode(LeafNode("A"), InnerNode(LeafNode("B"), LeafNode("C")))
-}
```
Orc built-in Option type
```{- A datatype for optional values of type T -}

type Option[T] = Some(T) | None()

{-
NONRUNNABLE
-}
```