Tagged Union - Examples

Examples

Say we wanted to build a binary tree of integers. In ML, we would do this by creating a datatype like this:

datatype tree = Leaf | Node of (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, say, counts the number of nodes in the tree:

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

Read more about this topic:  Tagged Union

Famous quotes containing the word examples:

    It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.
    —G.C. (Georg Christoph)

    No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.
    André Breton (1896–1966)

    In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.
    Michel de Montaigne (1533–1592)