10.10.10  Type Variables

Sometimes a function does not really care about its types:

    fun swap (x,y) = (y,x);

The function swap simply accepts a tuple of two values and reverses them; it really doesn’t care whether they the two values are ints, floats, strings, or gigabyte sized databases.

Declaring such a function as something like

    (Int, Int) -> (Int, Int)

would waste most of its potential utility.

Mythryl uses type variables such as X, Y, Z to represent such don’t-care values, and will automatically infer for such a function a most general type of:

    (X, Y) -> (Y, X)

Type variables are often used explicitly when defining datastructures, to mark don’t-care slots.

For example, the typical sorted binary tree implementation cares about the types of its keys, because it must know how to compare them in order to implement insert correctly and in order to implement find and delete efficiently, but it cares not at all about the types of the values in the tree, which it merely stores and returns unexamined.

Thus, a typical binary tree sumtype declaration looks like:

    Binary_Tree(X)
        = LEAF
        | NODE { key:   Float,
                 value: X,
                 left_kid:  Binary_Tree,
                 right_kid: Binary_Tree
               }
        ;

A user of such a tree will often declare explicitly the type of value in use:

    Int_Valued_Tree = Binary_Tree(Int);

Here Binary_Tree is serves as a compile-time function which constructs new types from old; consequently it is termed a type constructor.