We have seen Orc's predefined data structures: tuples, lists, and records. Orc also provides the capability for programmers to define their own data structures, using a feature adopted from the ML/Haskell language family called datatypes (also called variants or tagged sums).

Datatypes are defined using the type declaration:

type Tree = Node(_,_,_) | Empty()

This declaration defines two new sites named Node and Empty. Node takes three arguments, and publishes a tagged value wrapping those arguments. Empty takes no arguments and does the same.

Once we have created these tagged values, we use a new pattern called a datatype pattern to match them and unwrap the arguments:

type Tree = Node(_,_,_) | Empty()
{- Build up a small binary tree -}
val l = Node(Empty(), 0, Empty())
val r = Node(Empty(), 2, Empty())
val t = Node(l,1,r)

{- And then match it to extract its contents -}
t >Node(l,j,r)>
l >Node(_,i,_)>
r >Node(_,k,_)>
( i | j | k )

{-
OUTPUT:PERMUTABLE
0
1
2
-}

One pair of datatypes is so commonly used that it is already predefined in the standard library: Some(_) and None(). These are used as return values for calls that need to distinguish between successfully returning a value (Some(v)), and successfully completing but having no meaningful value to return (None()). For example, a lookup function might return Some(result) if it found a result, or return None() if it successfully performed the lookup but found no suitable result.