Tagged union

Incomputer science,atagged union,also called avariant,variant record,choice type,discriminated union,disjoint union,sum type,orcoproduct,is adata structureused 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 atagfield 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 representingtrees,where it is necessary to distinguish multi-node subtrees and leaves. Like ordinaryunions,tagged unions can save storage by overlapping storage areas for each type, since only one is in use at a time.

Description

Tagged unions are most important infunctional programminglanguages such asMLandHaskell,where they are calleddatatypes(seealgebraic data type) and thecompilercan verify that all cases of a tagged union are always handled, avoiding many types of errors. Compile-time checked sum types are also extensively used inRust,where they are calledenum.They can, however, be constructed in nearly anyprogramming language,and are much safer than untagged unions, often simply called unions, which are similar but do not explicitly track which member of a union is currently in use.

Tagged unions are often accompanied by the concept of aconstructor,which is similar but not the same as aconstructorfor aclass.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 todisjointordiscriminated unions,usually written using +. Given an element of a disjoint unionA+B,it is possible to determine whether it came fromAorB.If an element lies in both, there will be two effectively distinct copies of the value inA+B,one fromAand one fromB.

Intype theory,a tagged union is called asum type.Sum types are thedualofproduct types.Notations vary, but usually the sum type $A + B$ comes with two introduction forms (injections) $inj 1 : A \to A + B$ and $inj 2 : B \to A + B$ .The elimination form is case analysis, known aspattern matchinginML-stylelanguages: if $e$ has type $A + B$ and $e 1$ and $e 2$ have type $\tau$ under the assumptions $x : A$ and $y : B$ respectively, then the term ${\mathsf {case}}\ e\ {\mathsf {of}}\ x\Rightarrow e_{1}\mid y\Rightarrow e_{2}$ has type $\tau$ .The sum type corresponds tointuitionistic logical disjunctionunder theCurry–Howard correspondence.

Anenumerated typecan be seen as a degenerate case: a tagged union ofunit types.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, includingrope,lazy evaluation,class hierarchy(see below),arbitrary-precision arithmetic,CDR coding,theindirection bit,and other kinds oftagged pointers,are usually implemented using some sort of tagged union.

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

Advantages and disadvantages

The primary advantage of a tagged union over an untagged union is that all accesses are safe, and the compiler can even check that all cases are handled. Untagged unions depend on program logic to correctly identify the currently active field, which may result in strange behavior and hard-to-find bugs if that logic fails.

The primary advantage of a tagged union over a simplerecordcontaining 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 isimmutable,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 befolded,computedorencoded tags,where the tag value is dynamically computed from the contents of the union field. Common examples are the use ofreserved values,where, for example, a function returning a positive number may return -1 to indicate failure, andsentinel values,most often used intagged pointers.

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, auniversal data 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 asvariants.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.

Likeoption typesandexception handling,tagged unions are sometimes used to handle the occurrence of exceptional results. Often these tags are folded into the type asreserved 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 amonadwith the following functions:

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

{\text{bind}}\colon \left(A+E\right)\to \left(A\to \left(B+E\right)\right)\to \left(B+E\right)=a\mapsto f\mapsto {\begin{cases}{\text{err}}\,e&{\text{if}}\ a={\text{err}}\,e\\f\,a'&{\text{if}}\ a={\text{value}}\,a'\end{cases}}

where "value" and "err" are the constructors of the union type,AandBare valid result types andEis the type of error conditions. Alternately, the same monad may be described byreturnand two additional functions,fmapandjoin:

{\text{fmap}}\colon (A\to B)\to \left(\left(A+E\right)\to \left(B+E\right)\right)=f\mapsto a\mapsto {\begin{cases}{\text{err}}\,e&{\text{if}}\ a={\text{err}}\,e\\{\text{value}}\,{\text{(}}\,f\,a'\,{\text{)}}&{\text{if}}\ a={\text{value}}\,a'\end{cases}}

{\text{join}}\colon ((A+E)+E)\to (A+E)=a\mapsto {\begin{cases}{\text{err}}\,e&{\mbox{if}}\ a={\text{err}}\,e\\{\text{err}}\,e&{\text{if}}\ a={\text{value}}\,{\text{(err}}\,e\,{\text{)}}\\{\text{value}}\,a'&{\text{if}}\ a={\text{value}}\,{\text{(value}}\,a'\,{\text{)}}\end{cases}}

Examples

Say we wanted to build abinary treeof integers. In ML, we would do this by creating a datatype like this:

datatypetree=Leaf
|Nodeof(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:

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

Timeline of language support

1960s

InALGOL 68,tagged unions are calledunited modes,the tag is implicit, and thecaseconstruct is used to determine which field is tagged:

modenode=union(real,int,compl,string);

Usage example forunioncaseofnode:

noden:= "1234";

casenin
(realr): print(( "real:", r)),
(inti): print(( "int:", i)),
(complc): print(( "compl:", c)),
(strings): print(( "string:", s))
outprint(( "?:", n))
esac

1970s & 1980s

Functional programminglanguages such asML(from the 1970s) andHaskell(from the 1990s) give a central role to tagged unions and have the power to check that all cases are handled. Some other languages also support tagged unions.

Pascal,Ada,andModula-2call themvariant records(formallydiscriminated typein Ada), and require the tag field to be manually created and the tag values specified, as in this Pascal example:

typeshapeKind=(square,rectangle,circle);
shape=record
centerx:integer;
centery:integer;
casekind:shapeKindof
square:(side:integer);
rectangle:(width,height:integer);
circle:(radius:integer);
end;

and this Ada equivalent:

typeShape_Kindis(Square,Rectangle,Circle);
typeShape(Kind:Shape_Kind)isrecord
Center_X:Integer;
Center_Y:Integer;
caseKindis
whenSquare=>
Side:Integer;
whenRectangle=>
Width,Height:Integer;
whenCircle=>
Radius:Integer;
endcase;
end record;

-- 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.

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

enumShapeKind{Square,Rectangle,Circle};

structShape{
intcenterx;
intcentery;
enumShapeKindkind;
union{
struct{intside;};/* Square */
struct{intwidth,height;};/* Rectangle */
struct{intradius;};/* Circle */
};
};

intgetSquareSide(structShape*s){
assert(s->kind==Square);
returns->side;
}

voidsetSquareSide(structShape*s,intside){
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-nullpointer.This may be compared to theoptiontype in ML or theMaybetype in Haskell, and can be seen as atagged pointer:a tagged union (with an encoded tag) of two types:

Valid pointers,
Anull pointertype with only one value,null,indicating an exceptional condition.

Unfortunately, C compilers do not verify that the null case is always handled. This is a particularly common source of errors in C code, since there is a tendency to ignore exceptional cases.

2000s

One advanced dialect of C, calledCyclone,has extensive built-in support for tagged unions.^[1]

The enum types in theRust,Haxe,andSwiftlanguages also work as tagged unions.

The variant library from theBoost C++ Librariesdemonstrated it was possible to implement a safe tagged union as a library in C++, visitable using function objects.

structdisplay:boost::static_visitor<void>
{
voidoperator()(inti)
{
std::cout<<"It's an int, with value"<<i<<std::endl;
}

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

boost::variant<int,std::string>v=42;
boost::apply_visitor(display(),v);

boost::variant<int,std::string>v="hello world";
boost::apply_visitor(display(),v);

Scalahas case classes:

sealedabstractclassTree
caseobjectLeafextendsTree
caseclassNode(value:Int,left:Tree,right:Tree)extendsTree

valtree=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:

treematch{
caseNode(x,_,_)=>println("top level node value:"+x)
caseLeaf=>println("top level node is a leaf")
}

Scala's case classes also permit reuse through subtyping:

sealedabstractclassShape(centerX:Int,centerY:Int)
caseclassSquare(side:Int,centerX:Int,centerY:Int)extendsShape(centerX,centerY)
caseclassRectangle(length:Int,height:Int,centerX:Int,centerY:Int)extendsShape(centerX,centerY)
caseclassCircle(radius:Int,centerX:Int,centerY:Int)extendsShape(centerX,centerY)

F#has discriminated unions:

typeTree=
|Leaf
|Nodeofvalue:int*left:Tree*right:Tree

lettree=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:

matchtreewith
|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:^[2]

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

These can be matched using a switch expression:

switch(color){
caseRed:trace("Color was red");
caseGreen:trace("Color was green");
caseBlue:trace("Color was blue");
caseRgb(r,g,b):trace("Color had a red value of"+r);
}

Nimhas object variants^[3]similar in declaration to those in Pascal and Ada:

type
ShapeKind=enum
skSquare,skRectangle,skCircle
Shape=object
centerX,centerY:int
casekind:ShapeKind
ofskSquare:
side:int
ofskRectangle:
length,height:int
ofskCircle:
radius:int

Macroscan be used to emulate pattern matching or to create syntactic sugar for declaring object variants, seen here as implemented by the packagepatty:

importpatty

proc`~`[A](a:A):refA=
new(result)
result[]=a

variantList[A]:
Nil
Cons(x:A,xs:refList[A])

proclistHelper[A](xs:seq[A]):List[A]=
ifxs.len==0:Nil[A]()
else:Cons(xs[0],~listHelper(xs[1..xs.high]))

proclist[A](xs:varargs[A]):List[A]=listHelper(@xs)

procsum(xs:List[int]):int=(block:
matchxs:
Nil:0
Cons(y,ys):y+sum(ys[])
)

echosum(list(1,2,3,4,5))

2010s

Enums are added in Scala 3,^[4]allowing us to rewrite the earlier Scala examples more concisely:

enumTree[+T]:
caseLeaf
caseNode(x:Int,left:Tree[T],right:Tree[T])

enumShape(centerX:Int,centerY:Int):
caseSquare(side:Int,centerX:Int,centerY:Int)extendsShape(centerY,centerX)
caseRectangle(length:Int,height:Int,centerX:Int,centerY:Int)extendsShape(centerX,centerY)
caseCircle(radius:Int,centerX:Int,centerY:Int)extendsShape(centerX,centerY)

TheRust languagehas extensive support for tagged unions, called enums.^[5]For example:

enumTree{
Leaf,
Node(i64,Box<Tree>,Box<Tree>)
}

It also allows matching on unions:

lettree=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)))))
);

fnadd_values(tree:Tree)->i64{
matchtree{
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 theOption<T>type, which is eitherNoneorSome(T),and theResult<T, E>type, which is eitherOk(T)orErr(E).^[6]

Swiftalso has substantial support for tagged unions via enumerations.^[7]For example:

enumTree{
caseleaf
indirectcasenode(Int,Tree,Tree)
}

lettree=Tree.node(
2,
.node(0,.leaf,.leaf),
.node(3,.leaf,.node(4,.leaf,.leaf))
)

funcadd_values(_tree:Tree)->Int{
switchtree{
caselet.node(v,a,b):
returnv+add_values(a)+add_values(b)

case.leaf:
return0
}
}

assert(add_values(tree)==9)

WithTypeScriptit is also possible to create tagged unions. For example:

interfaceLeaf{kind:"leaf";}

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

typeTree=Leaf|Node

constroot: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"}
}
}
}

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

Python 3.9introduces support for typing annotations that can be used to define a tagged union type (PEP-593^[8]):

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

C++17introduces std::variant andconstexpr if

usingTree=std::variant<structLeaf,structNode>;

structLeaf
{
std::stringvalue;
};
structNode
{
Tree*left=nullptr;
Tree*right=nullptr;
};

structTransverser
{
template<typenameT>
voidoperator()(T&&v)
{
ifconstexpr(std::is_same_v<T,Leaf&>)
{
std::cout<<v.value<<"\n";
}
elseifconstexpr(std::is_same_v<T,Node&>)
{
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!");
};
}
};
/*Tree forest =...;
std::visit(Transverser{}, forest);*/

Class hierarchies as tagged unions

In a typicalclass hierarchyinobject-oriented programming,each subclass can encapsulate data unique to that class. The metadata used to performvirtual methodlookup (for example, the object'svtablepointer in most C++ implementations) identifies the subclass and so effectively acts as a tag identifying the data stored by the instance (seeRTTI). An object'sconstructorsets this tag, and it remains constant throughout the object's lifetime.

Nevertheless, a class hierarchy involves truesubtype polymorphism.It can be extended by creating further subclasses of the same base type, which could not be handled correctly under a tag/dispatch model. Hence, it is usually not possible to do case analysis or dispatch on a subobject's 'tag' as one would for tagged unions. Some languages such asScalaallow base classes to be "sealed", and unify tagged unions with sealed base classes.

References

^"Cyclone: Tagged Unions".
^"Using Enums - Haxe - The Cross-platform Toolkit".Haxe Foundation.
^"Nim Manual".nim-lang.org.Retrieved2020-01-23.
^"Scala 3 Language Reference: Enumerations".The Scala Team.
^"The Rust Programming Language".Mozilla.
^"Rust By Example".Mozilla.
^"Enumerations — The Swift Programming Language (Swift 5.4)".docs.swift.org.Retrieved2021-04-28.
^"PEP 593 -- Flexible function and variable annotations".Python.org.Retrieved2021-06-20.

External links

boost::variantis a C++ typesafe discriminated union
std.variantis an implementation of variant type inD2.0

[1] "Cyclone: Tagged Unions".

[2] "Using Enums - Haxe - The Cross-platform Toolkit".Haxe Foundation.

[3] "Nim Manual".nim-lang.org.Retrieved2020-01-23.

[4] "Scala 3 Language Reference: Enumerations".The Scala Team.

[5] "The Rust Programming Language".Mozilla.

[6] "Rust By Example".Mozilla.

[7] "Enumerations — The Swift Programming Language (Swift 5.4)".docs.swift.org.Retrieved2021-04-28.

[8] "PEP 593 -- Flexible function and variable annotations".Python.org.Retrieved2021-06-20.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v t e Data types
Uninterpreted	Bit Byte Trit Tryte Word Bit array
Numeric	Arbitrary-precision or bignum Complex Decimal Fixed point Floating point Reduced precision Minifloat Half precision bfloat16 Single precision Double precision Quadruple precision Octuple precision Extended precision Long double Integer signedness Interval Rational
Pointer	Address physical virtual Reference
Text	Character String null-terminated
Composite	Algebraic data type generalized Array Associative array Class Dependent Equality Inductive Intersection List Object metaobject Option type Product Record or Struct Refinement Set Union tagged
Other	Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Strongly typed identifier Top type Type class Empty type Unit type Void
Related topics	Abstract data type Bo xing Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Interface Subtyping Type constructor Type conversion Type system Type theory Variable