Discriminated unions and match

One of several shapes

A discriminated union says that a value is one of a fixed set of cases, and each case may carry data: type Shape = | Circle of int | Rect of int * int. A circle carries one number, a rectangle two. The cases are the only possibilities there are.

This is not a class hierarchy. There is no base type to cast to and no method to override: a Shape is a Shape, and the only way to reach the number inside is to match on the case that carries it. That sounds restrictive until you notice what it removes — the field that is only sometimes filled in, the type tag that can disagree with the fields, the cast that can fail.

match, with every case accounted for

match shape with | Circle r -> ... | Rect (w, h) -> ... takes the value apart and binds whatever each case carries. One branch per case and the match is complete; leave one out and the compiler warns, naming the case you missed. Add a fifth case to a union and every match that ignores it starts warning, so the code tells you where the new possibility has to be handled.

A function per question, each one a match, is the shape of this style: area answers a number, name answers a string, and both are total — every shape has an area and a name, and no branch has to answer "not applicable". A case that carries no data is written without of, and its pattern is just the name.

A final _ branch makes a match complete and also silences the warning that would have told you a case was added. Use it when the remaining cases really share one answer, and leave it out when each case deserves its own branch; the warning is the compiler doing the work of finding every place a new possibility has to be considered.

A union, and two total functions over it

type Shape =
    | Circle of int
    | Rect of int * int

let area shape =
    match shape with
    | Circle r -> 3 * r * r
    | Rect (w, h) -> w * h

A case can hold the same type again

A union may refer to itself. type Tree = | Leaf of int | Node of Tree * Tree says a tree is either a leaf holding a number or a node holding two smaller trees. The definition is finite even though the values are not, because every recursive step has to end at a leaf.

Functions over such a value are recursive in the same shape. The leaf branch is the base case and returns without calling again; the node branch calls the function on both children and combines the answers. The structure of the type tells you how many recursive calls the function needs, which is why the definition is worth reading before the code.

A case name is also a constructor function. Leaf takes an int and answers a Tree; Node takes a pair of trees. That is why Node (Leaf 3, Leaf 4) builds a value without any new, and why the same names appear in patterns.

The shape rules out the impossible states

The alternative is a tag plus fields that are only meaningful for some tags: a kind string, a radius that is zero for rectangles, a width that is meaningless for circles. Nothing stops the tag and the fields from disagreeing, and every function has to remember which fields are real.

With a union there is no tag to disagree with the data. A Circle carries a radius and nothing else, and the only way to reach it is to match on that case. The compiler then checks every match against every case, so the cost of adding a possibility is paid where it belongs: at the functions that must decide what it means.

Try these next

• Add a Tri of int * int case to the shape union and let the warnings list every function that needs a branch.
• Write let rec count tree that answers how many leaves a tree has.
• Build a tree with four leaves and check its total and depth by hand before running.