TITLE: What are descriminated unions? PROBLEM: chris@double.actrix.gen.nz (Chris Double) What are discriminated unions? At a guess it sounds like a union of types and some sort of identifier saying which type is actually stored in the union. Is this correct? RESPONSE: fjh@munta.cs.mu.OZ.AU (Fergus Henderson), 12 Apr 95 Yes, roughly speaking, and that's one way of implementing discriminated unions in C++. Mathematically, if you consider types as sets of values, then a discriminated union D of types T_1, T_2, ..., T_n is the set D = ({ tag_1 } x T_1) U ({ tag_2 } x T2 } U ... U ({ tag_n } x T_n) where `tag_1' thru `tag_n' are distinct (but otherwise arbitrary) constants, (`x' denotes cross-product, `U' denotes set union, and `{ X }' denotes the set containing just X.) Note that enumerations are equivalent to a special case of discriminated unions, when all the T_i are the unit type. Another way of implementing discriminated unions in C++ is with inheritence. All the types T_1 ... T_n are derived from a common abstract base class. An element of the discriminated union is represented by a pointer or reference to the base class, and you use RTTI to determine which of the different possibilities it actually refers to. QUESTION: chris@double.actrix.gen.nz (Chris Double) What sort of area you would use this in? RESPONSE: fjh@munta.cs.mu.OZ.AU (Fergus Henderson) Whenever a piece of data could be one of a finite, stable set of alternatives. If it could be one of an unbounded or unstable set of alternatives, then you should generally use subtyping implemented as inheritence from an abstract base class (and in this case, you should generally _not_ use RTTI). In languages with good support for discriminated unions, the most commonly used examples are types like lists and trees. For example, a list of integers is either empty (`nil'), or it is constructed (`cons') from an integer followed by another intlist: datatype intlist = nil | cons of int * intlist ; I've borrowed SML syntax. Note that the `*' in `int * intlist' is a cross-product, i.e. the type `int * intlist' is just a pair consisting of an int and an intlist. With the above definition, you can write expressions of type intlist such as `nil', which represents the empty list, and `cons(1, cons(2, cons(3, nil)))', which represents the list 1, 2, 3. You can also write functions which act on this recursive data structure, such as a function to compute the length of a list: fun length (list) = case list of nil => 0 cons (head, tail) => length (tail) + 1; Another example is a 2-3 tree, which can contain nodes with either two or three children: datatype tree = empty | two_node of tree * int * tree | three_node of tree * int * tree * int * tree ; Another example, from a hypothetical card came: datatype suit = spades | clubs | diamonds | hearts ; datatype card = card of suit * rank | joker ;