Discriminated Union

In the next sample we demonstrate working with the discriminated union type. This type is used for representing a data type that store one of several possible options (where the options are well known when writing the code). One common example of data type that can be represented using discriminated unions is an abstract syntax tree (i.e. an expression in some programming language):


> // Declaration of the 'Expr' type
type Expr =
| Binary of string * Expr * Expr
| Variable of string
| Constant of int;;
(...)
> // Create a value 'v' representing 'x + 10'
let v = Binary("+", Variable "x", Constant 10);;
val v : Expr

To work with the values of a discriminated union type, we can again use pattern matching. In this case we use the match language construct, which can be used for testing a value against several possible patterns – in case of the Expr type, the possible options are determined by all identifiers used when declaring the type (these are called constructors), namely Binary, Variable and Constant. The following example declares a function eval, which evaluates the given expression (assuming that getVariableValue is a function that returns a value of variable):

> let rec eval x =
match x with
| Binary(op, l, r) ->
let (lv, rv) = (eval l, eval r)
if (op = "+") then lv + rv
elif (op = "-") then lv - rv
else failwith "Unknonw operator!"
| Variable(var) ->
getVariableValue var
| Constant(n) ->
n;;
val eval : Expr -> int


When declaring a function we can use the let keyword that is used for binding a value to a name. I don’t use a term variable known from other programming languages for a reason that will be explained shortly. When writing a recursive function, we have to explicitly state this using the rec keyword as in the previous example.
Discriminated unions form a perfect complement to the typical object-oriented inheritance structure. In an OO hierarchy the base class declares all methods that are overridden in derived classes, meaning that it is easy to add new type of value (by adding a new inherited class), but adding a new operation requires adding method to all the classes. On the other side, a discriminated union defines all types of values in advance, which means that adding a new function to work with the type is easy, but adding a new type of value (new constructor to the discriminated union) requires modification of all existing functions. This suggests that discriminated unions are usually a better way for implementing a Visitor design pattern in F#.