Exercise #5

Algebraic datatypes and `case` deconstruction

SML allows a certain class of types, called algebraic datatypes, to be defined by users. An example of this is

datatype bool = true | false;

which simply defines the bool type as we already know it. Thus, datatype declarations can be used to introduce new enumeration types.
It is also possible to store values along with enumerations, as in

datatype something = some_int  of int
                   | some_real of real
		   | some_bool of bool;

which allows this type to be used as a discriminated union.
As a third example, one could try to re-implement lists of integers as follows:

datatype int_list = nil
                  | cons of (int * int_list);

Note that, in the above, nil, cons, true, false, some_int, some_real and some_bool are constructors in the same sense as (::) for lists was earlier-- this means that they can be part of patterns for pattern matching.

Design a type for a binary tree with undecorated inner nodes and int values as its leaves, and describe it in terms of a datatype.
Using pattern matching, implement a function which traverses this tree and computes the product of all leaf nodes.
Standard ML comes with a case construct for pattern matching within a function. This construct looks like the following:
```
    case <value> of
        <option> => <expression>
	...
      | <option> => <expression>
```
and behaves like pattern matching on functions. In order to familiarise yourself with it, implement a function ifthenelse: bool * int * int -> int which uses a case construct to determine which of its arguments it should return, based on whether the first argument is true or false. Will your function really behave like a regular if...then...else... construction if one of the arguments produces a side effect or doesn't terminate?
Using both kinds of pattern matching, implement a function which traverses this tree and computes, for each inner node, the result of integer-dividing the result of the left-hand side by the result of the right-hand side (i.e., recurse left, recurse right, and divide the left-recursion result by the right recursion one). Use the infix (div): int * int -> int to divide integers. If you encounter a 0 on the right-hand side, return 0 instead of dividing by zero.

Standard ML is installed at /tools/cs/smlnj/bin/sml on the CSEL machines.

Exercise #5

Algebraic datatypes and case deconstruction

Algebraic datatypes and `case` deconstruction