Typedef

You can declare new composite types. For example if we didn't have lists built in:

typedef lst(#t) { pair(#t, lst(#t)) | null }

Creates a new type lst(#t) (list of t) and two constructors pair and null that construct values of that type.#t is a type variable and stands for any type during the definition.

Given the above, you can create a lst of integers like this:

pair(1, pair(2, pair(3, null)))

Much like constants, type constructors can be used in the formal arguments to composite functions, where they act as templates for the actual arguments. This plays well with the pattern matching discussed previously:

fn lst_map {
    (f, null) { null }
    (f, pair(h, t)) { pair(f(h), lst_map(f, t)) }
}

Note the type of lst_map is polymorphic: (#a -> #b) -> lst(#a) -> lst(#b), it doesn't care about the actual types of #a and #b (see Type Notation for a discussion of ->).

Here's another example, using typedef to create an enumeration:

typedef colours { red | green | blue }

fn colour_to_string {
    (red) { "red" }
    (green) { "green" }
    (blue) { "blue" }
}

Type constructors that take no arguments, like red, green and blue above, behave as constants of the given type (colours in this case.)

Here's yet another example, creating a binary tree with an insert function

typedef tree(#t) { branch(tree(#t), #t, tree(#t)) | leaf }

fn insert {
    (v, leaf) {
        branch(leaf, v, leaf)
    }
    (v, x = branch(left, v, right)) {
        x
    }
    (v, branch(left, u, right)) {
        if (v < u) {
            branch(insert(v, left), u, right)
        } else {
            branch(left, u, insert(v, right))
        }
    }
}

insert(1, insert(3, insert(2, insert(4, leaf))));

is

branch(
    branch(
        branch(leaf, 1, leaf),
        2,
        branch(leaf, 3, leaf)
    ),
    4,
    leaf
)

Again the type of insert is polymorphic: #t -> tree(#t) -> tree(#t), e.g. it doesn't care what type #t is, as long as it's consistent and supports the < operator.

As a final, more complete example, this gist which is copied from a running test, shows a lambda interpreter for a very small language written in F♮ making use of typedef.

Predefined Types

The basic built-in types int, char, bool, nothing and list(t) are available when you want to constrain the types in a typedef more tightly. For example:

typedef named_list(#t) { named(list(char), list(#t)) }

Additionally, the pseudo-type string is provided as an alias for list(char) so the following example does exactly the same thing as the previous one:

typedef named_list(#t) { named(string, list(#t)) }

Mixed Types

It was noted earlier that lists for example can only be of a single type, but the typedef construct allows us to get around that restriction in a type safe way. For example:

typedef either(#t, #u) { type_a(#t) | type_b(#u) }

Allows us to create lists like:

define mix = [ type_a(1), type_a(2), type_b("hello"), type_b("goodbye") ];

After this, the type of mix is list(either(int, string)). you could for example map over this list with a function like:

fn len_or_val {
    (type_a(v)) { v }
    (type_b(v)) { length(v) }
}

Which is of type either(int, list(#a)) -> int.

Up: Home

Next: First Class Environments