Tagged union

 ( Data Types ) 

In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type, or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. Only one of the types can be in use at any one time, and a tag field explicitly indicates which type is in use. It can be thought of as a type that has several "cases", each of which should be handled correctly when that type is manipulated. This is critical in defining recursive datatypes, in which some component of a value may have the same type as that value, for example in defining a type for representing trees, where it is necessary to distinguish multi-node subtrees and leaves. Like ordinary Union type, tagged unions can save storage by overlapping storage areas for each type, since only one is in use at a time.

Tagged unions are often accompanied by the concept of a constructor, which is similar but not the same as a constructor for a class. A constructor is a function or an expression that produces a value of the tagged union type, given a tag and a value of the corresponding type.

Mathematically, tagged unions correspond to disjoint union or discriminated unions, usually written using +. Given an element of a disjoint union A + B, it is possible to determine whether it came from A or B. If an element lies in both, there will be two effectively distinct copies of the value in A + B, one from A and one from B.

In type theory, a tagged union is called a sum type. Sum types are the dual of . Notations vary, but usually the sum type comes with two introduction forms (injections) and The elimination form is case analysis, known as pattern matching in ML-style languages: if has type and and have type $\backslash tau$ under the assumptions and respectively, then the term $\backslash mathsf\{case\}\backslash \; e\backslash \; \backslash mathsf\{of\}\backslash \; x\; \backslash Rightarrow\; e\_1\; \backslash mid\; y\; \backslash Rightarrow\; e\_2$ has type $\backslash tau$. The sum type corresponds to intuitionistic logical disjunction under the Curry–Howard correspondence.

An enumerated type can be seen as a degenerate case: a tagged union of . It corresponds to a set of nullary constructors and may be implemented as a simple tag variable, since it holds no additional data besides the value of the tag.

Many programming techniques and data structures, including rope, lazy evaluation, class hierarchy (see below), arbitrary-precision arithmetic, CDR coding, the indirection bit, and other kinds of , are usually implemented using some sort of tagged union.

A tagged union can be seen as the simplest kind of self-describing data format. The tag of the tagged union can be seen as the simplest kind of metadata.

The primary advantage of a tagged union over a simple record containing a field for each type is that it saves storage by overlapping storage for all the types. Some implementations reserve enough storage for the largest type, while others dynamically adjust the size of a tagged union value as needed. When the value is Immutable object, it is simple to allocate just as much storage as is needed.

The main disadvantage of tagged unions is that the tag occupies space. Since there are usually a small number of alternatives, the tag can often be squeezed into 2 or 3 bits wherever space can be found, but sometimes even these bits are not available. In this case, a helpful alternative may be folded, computed or encoded tags, where the tag value is dynamically computed from the contents of the union field. Common examples are the use of reserved values, where, for example, a function returning a positive number may return -1 to indicate failure, and , most often used in .

Sometimes, untagged unions are used to perform bit-level conversions between types, called reinterpret casts in C++. Tagged unions are not intended for this purpose; typically a new value is assigned whenever the tag is changed.

Many languages support, to some extent, a Top type, which is a type that includes every value of every other type, and often a way is provided to test the actual type of a value of the universal type. These are sometimes referred to as variants. While universal data types are comparable to tagged unions in their formal definition, typical tagged unions include a relatively small number of cases, and these cases form different ways of expressing a single coherent concept, such as a data structure node or instruction. Also, there is an expectation that every possible case of a tagged union will be dealt with when it is used. The values of a universal data type are not related and there is no feasible way to deal with them all.

Like and exception handling, tagged unions are sometimes used to handle the occurrence of exceptional results. Often these tags are folded into the type as reserved values, and their occurrence is not consistently checked: this is a fairly common source of programming errors. This use of tagged unions can be formalized as a monad with the following functions:

$\backslash text\{return\}\backslash colon\; A\; \backslash to\; \backslash left(\; A\; +\; E\; \backslash right)\; =\; a\; \backslash mapsto\; \backslash text\{value\}\; \backslash ,\; a$

where "value" and "err" are the constructors of the union type, A and B are valid result types and E is the type of error conditions. Alternately, the same monad may be described by return and two additional functions, fmap and join:

datatype tree = Leaf

             | Node of (int * tree * tree)
     

This is a tagged union with two cases: one, the leaf, is used to terminate a path of the tree, and functions much like a null value would in imperative languages. The other branch holds a node, which contains an integer and a left and right subtree. Leaf and Node are the constructors, which enable us to actually produce a particular tree, such as:

Node(5, Node(1, Leaf, Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))

which corresponds to this tree:

Now we can easily write a typesafe function that, for example, counts the number of nodes in the tree:

fun countNodes(Leaf) = 0

 | countNodes(Node(int, left, right)) =
     1 + countNodes(left) + countNodes(right)
     

'''mode''' '''node''' = '''union''' ('''real''', '''int''', '''compl''', '''string''');

Usage example for '''union''' '''case''' of '''node''':

'''node''' n := "1234";
 
'''case''' n '''in'''
  ('''real''' r):   print(("real:", r)),
  ('''int''' i):    print(("int:", i)),
  ('''compl''' c):  print(("compl:", c)),
  ('''string''' s): print(("string:", s))
  '''out'''         print(("?:", n))
'''esac'''
     

Pascal, Ada, and Modula-2 call them variant records (formally discriminated type in Ada), and require the tag field to be manually created and the tag values specified, as in this Pascal example:

type shapeKind = (square, rectangle, circle);

    shape = record
               centerx : integer;
               centery : integer;
               case kind : shapeKind of
                  square : (side : integer);
                  rectangle : (width, height : integer);
                  circle : (radius : integer);
      end;
     

and this Ada equivalent: type Shape_Kind is (Square, Rectangle, Circle); type Shape (Kind : Shape_Kind) is record

  Center_X : Integer;
  Center_Y : Integer;
  case Kind is
     when Square =>
        Side : Integer;
     when Rectangle =>
        Width, Height : Integer;
     when Circle =>
        Radius : Integer;
  end case;
     

-- Any attempt to access a member which existence depends -- on a certain value of the discriminant, while the -- discriminant is not the expected one, raises an error.

In C and C++, a tagged union can be created from untagged unions using a strict access discipline where the tag is always checked:

enum ShapeKind { Square, Rectangle, Circle };

struct Shape {

   int centerx;
   int centery;
   enum ShapeKind kind;
   union {
       struct { int side; };           /* Square */
       struct { int width, height; }; /* Rectangle */
       struct { int radius; };         /* Circle */
   };
     

int getSquareSide(struct Shape* s) {

   assert(s->kind == Square);
   return s->side;
     

void setSquareSide(struct Shape* s, int side) {

   s->kind = Square;
   s->side = side;
     

/* and so on */

As long as the union fields are only accessed through the functions, the accesses will be safe and correct. The same approach can be used for encoded tags; we simply decode the tag and then check it on each access. If the inefficiency of these tag checks is a concern, they may be automatically removed in the final version.

C and C++ also have language support for one particular tagged union: the possibly-null pointer. This may be compared to the option type in ML or the Maybe type in Haskell, and can be seen as a tagged pointer: a tagged union (with an encoded tag) of two types:

• Valid pointers,
• A null pointer type with only one value, null, indicating an exceptional condition.

The enum types in the Rust, Haxe, and Swift languages also work as tagged unions.

The variant library from the Boost C++ Libraries demonstrated it was possible to implement a safe tagged union as a library in C++, visitable using function objects. struct display : boost::static_visitor {

   void operator()(int i)
   {
       std::cout << "It's an int, with value " << i << std::endl;
   }
     

   void operator()(const std::string& s)
   {
       std::cout << "It's a string, with value " << s << std::endl;
   }
     

boost::variant v = 42; boost::apply_visitor(display(), v);

boost::variant v = "hello world"; boost::apply_visitor(display(), v);

Scala has case classes: sealed abstract class Tree case object Leaf extends Tree case class Node(value: Int, left: Tree, right: Tree) extends Tree

val tree = Node(5, Node(1, Leaf, Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))

Because the class hierarchy is sealed, the compiler can check that all cases are handled in a pattern match: tree match {

 case Node(x, _, _) => println("top level node value: " + x)
 case Leaf          => println("top level node is a leaf")
     

Scala's case classes also permit reuse through subtyping:

sealed abstract class Shape(centerX: Int, centerY: Int) case class Square(side: Int, centerX: Int, centerY: Int) extends Shape(centerX, centerY) case class Rectangle(length: Int, height: Int, centerX: Int, centerY: Int) extends Shape(centerX, centerY) case class Circle(radius: Int, centerX: Int, centerY: Int) extends Shape(centerX, centerY)

F# has discriminated unions:

type Tree =

 | Leaf
 | Node of value: int * left: Tree * right: Tree
     

let tree = Node(5, Node(1, Leaf, Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))

Because the defined cases are exhaustive, the compiler can check that all cases are handled in a pattern match: match tree with | Node (x, _, _) -> printfn "top level node value: %i" x | Leaf -> printfn "top level node is a leaf"

Haxe's enums also work as tagged unions: enum Color {

 Red;
 Green;
 Blue;
 Rgb(r:Int, g:Int, b:Int);
     

These can be matched using a switch expression: switch (color) {

 case Red: trace("Color was red");
 case Green: trace("Color was green");
 case Blue: trace("Color was blue");
 case Rgb(r, g, b): trace("Color had a red value of " +r);
     

 ShapeKind = enum
   skSquare, skRectangle, skCircle
 Shape = object
   centerX, centerY: int
   case kind: ShapeKind
   of skSquare:
     side: int
   of skRectangle:
     length, height: int
   of skCircle:
     radius: int
     

 new(result)
 result[] = a
     

 Nil
 Cons(x: A, xs: ref List[A])
     

 if xs.len == 0: Nil[A]()
 else: Cons(xs[0], ~listHelper(xs[1 .. xs.high]))
     

 match xs:
   Nil: 0
   Cons(y, ys): y + sum(ys[])
     

 case Leaf
 case Node(x: Int, left: Tree[T], right: Tree[T])
     

 case Square(side: Int, centerX: Int, centerY: Int) extends Shape(centerY, centerX)
 case Rectangle(length: Int, height: Int, centerX: Int, centerY: Int) extends Shape(centerX, centerY)
 case Circle(radius: Int, centerX: Int, centerY: Int) extends Shape(centerX, centerY)
     

   Leaf,
   Node(i64, Box, Box)
     

It also allows matching on unions:

let tree = Tree::Node(

   2,
   Box::new(Tree::Node(0, Box::new(Tree::Leaf), Box::new(Tree::Leaf))),
   Box::new(Tree::Node(3, Box::new(Tree::Leaf),
       Box::new(Tree::Node(4, Box::new(Tree::Leaf), Box::new(Tree::Leaf)))))
     

fn add_values(tree: Tree) -> i64 {

   match tree {
       Tree::Node(v, a, b) => v + add_values(*a) + add_values(*b),
       Tree::Leaf => 0
   }
     

assert_eq!(add_values(tree), 9);

Rust's error handling model relies extensively on these tagged unions, especially the Option<T> type, which is either None or Some(T), and the Result<T, E> type, which is either Ok(T) or Err(E).

Swift also has substantial support for tagged unions via enumerations. For example: enum Tree {

   case leaf
   indirect case node(Int, Tree, Tree)
     

let tree = Tree.node(

   2,
   .node(0, .leaf, .leaf),
   .node(3, .leaf, .node(4, .leaf, .leaf))
     

func add_values(_ tree: Tree) -> Int {

   switch tree {
   case let .node(v, a, b):
       return v + add_values(a) + add_values(b)
     

   case .leaf:
       return 0
   }
     

assert(add_values(tree) == 9)

With TypeScript it is also possible to create tagged unions. For example:

interface Leaf { kind: "leaf"; }

interface Node { kind: "node"; value: number; left: Tree; right: Tree; }

type Tree = Leaf | Node

const root: Tree = {

 kind: "node",
 value: 5,
 left: {
   kind: "node",
   value: 1,
   left: { kind: "leaf" },
   right: { kind: "leaf" }
 },
 right: {
   kind: "node",
   value: 3,
   left: { kind: "leaf" },
   right: {
     kind: "node",
     value: 4,
     left: { kind: "leaf" },
     right: { kind: "leaf" }
   }
 }
     

function visit(tree: Tree) {

   switch (tree.kind) {
       case "leaf":
           break
       case "node":
           console.log(tree.value)
           visit(tree.left)
           visit(tree.right)
           break
   }
     

   TypedDict('Currency', {'dollars': float, 'pounds': float}, total=False),
   TaggedUnion,
     

 std::string value;
     

 Tree* left = nullptr;
 Tree* right = nullptr;
     

 template
 void operator()(T&& v)
 {
   if constexpr (std::is_same_v)
   {
     std::cout << v.value << "\n";
   }
   else if constexpr (std::is_same_v)
   {
     if (v.left != nullptr)
       std::visit(Transverser{}, *v.left);
     

     if (v.right != nullptr)
       std::visit(Transverser{}, *v.right);
   }
   else
   {
     // The !sizeof(T) expression is always false
     static_assert(!sizeof(T), "non-exhaustive visitor!");
   };
 }
     

 std::visit(Transverser{}, forest);*/