Tagged union

Tagged unions are most important in functional programming languages such as ML and Haskell, where they are called datatypes (see algebraic data type) and the compiler can verify that all cases of a tagged union are always handled, avoiding many types of errors.

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 tagged pointers, are usually implemented using some sort of tagged union.

Some implementations reserve enough storage for the largest type, while others dynamically adjust the size of a tagged union value as needed.

Sometimes, untagged unions are used to perform bit-level conversions between types, called reinterpret casts in C++.

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.

The values of a universal data type are not related and there is no feasible way to deal with them all.

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.

Alternately, the same monad may be described by return and two additional functions, fmap and join: Say we wanted to build a binary tree of integers.

In ML, we would do this by creating a datatype like this: 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.

Leaf and Node are the constructors, which enable us to actually produce a particular tree, such as: which corresponds to this tree: Now we can easily write a typesafe function that, for example, counts the number of nodes in the tree: In ALGOL 68, tagged unions are called united modes, the tag is implicit, and the case construct is used to determine which field is tagged: mode node = union (real, int, compl, string); Usage example for union case of node: Functional programming languages such as ML (from the 1970s) and Haskell (from the 1990s) give a central role to tagged unions and have the power to check that all cases are handled.

One advanced dialect of C, called Cyclone, has extensive built-in support for tagged unions.

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

Scala has case classes: Because the class hierarchy is sealed, the compiler can check that all cases are handled in a pattern match: Scala's case classes also permit reuse through subtyping: F# has discriminated unions: Because the defined cases are exhaustive, the compiler can check that all cases are handled in a pattern match: Haxe's enums also work as tagged unions:[2] These can be matched using a switch expression: Nim has object variants[3] similar in declaration to those in Pascal and Ada:Macros can be used to emulate pattern matching or to create syntactic sugar for declaring object variants, seen here as implemented by the package patty:Enums are added in Scala 3,[4] allowing us to rewrite the earlier Scala examples more concisely: The Rust language has extensive support for tagged unions, called enums.

For example: Python 3.9 introduces support for typing annotations that can be used to define a tagged union type (PEP-593[8]): C++17 introduces std::variant and constexpr ifIn a typical class hierarchy in object-oriented programming, each subclass can encapsulate data unique to that class.

The metadata used to perform virtual method lookup (for example, the object's vtable pointer in most C++ implementations) identifies the subclass and so effectively acts as a tag identifying the data stored by the instance (see RTTI).

It can be extended by creating further subclasses of the same base type, which could not be handled correctly under a tag/dispatch model.