Typedef

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

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)))

In fact, the list type is not built in, it is defined exactly like this in a standard preamble, specifically as:

typedef list(#t) { nil | cons(#t, list(#t)) }

[] and @ being just syntactic sugar for calls to nil and cons.

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 ->).

The sugared constructors are also usable here, so map in the listutils.fn library is

fn map {
  (_, [])    { [] }
  (f, h @ t) { f(h) @ map(f, t) }
}

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

let
    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))
            }
        }
    }
in
    print(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 shows a lambda interpreter for a very small language written in F♮ making use of typedef.

Predefined Types

The basic built-in types number and char, as well as predefined library types like bool 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)) }

The pseudo-type string is an alias for list(char) so the following example will do 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) { left(#t) | right(#u) }

Allows us to create lists like:

mix = [ left(1), left(2), right("hello"), right("goodbye") ];

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

fn len_or_val {
    (left(v)) { v }
    (right(v)) { list.length(v) }
}

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

The maybe type

Another great example is the maybe type. This is defined in the preamble:

typedef maybe(#t) { nothing | some(#t) }

This can be very useful when writing functions like a dictionary lookup that can legitimately fail to find a value. Rather than relying on some special out-of-bounds value, or causing an error in this situation, you return a maybe of the value, forcing your caller to handle the situation:

// lookup:: dict(#k, #v) -> #k -> maybe(#v)
let
    fn lookup(dict, key) {
        ....
        some(value)
        ...
        nothing
    }
in
    ...
    switch(lookup(d, k)) {
        (some(v)) {
            // handle success
            print v
        }
        (nothing) {
            // handle failure
            print "not found"
        }
    }

Shorthand Syntax

When a typedef has exactly one constructor that shares the typedef's name, the body can be omitted. The parser expands the shorthand into the full form automatically.

Positional shorthand

Shorthand	Equivalent full form
typedef t;	typedef t { t }
typedef t(#a);	typedef t(#a) { t(#a) }
typedef t(char);	typedef t { t(char) }
typedef t(#a, char);	typedef t(#a) { t(#a, char) }
typedef t(#a, #b);	typedef t(#a, #b) { t(#a, #b) }

The rule: generic type variables (#name) appearing in the argument list are lifted to the typedef head in first-appearance order; non-generic (concrete) types remain only in the constructor argument list.

For example, a simple wrapper around a character value can be written as:

typedef labelled(#a, char)

which is equivalent to:

typedef labelled(#a) { labelled(#a, char) }

Tagged (named-field) shorthand

A typedef with a single named-field constructor can also use shorthand syntax. Write the field map directly after the typedef name:

typedef person{name: string, meta: #a}

which is equivalent to:

typedef person(#a) { person{name: string, meta: #a} }

The rule: generic type variables that appear as the complete type of a field (a plain #name) are lifted to the typedef head in left-to-right first-appearance order. Concrete types and nested type applications such as list(#a) remain only in the constructor field list.

Shorthand	Equivalent full form
typedef t{x: number};	typedef t { t{x: number} }
typedef t{x: #a};	typedef t(#a) { t{x: #a} }
typedef t{x: string, y: #a};	typedef t(#a) { t{x: string, y: #a} }
typedef t{x: #a, y: #b};	typedef t(#a, #b) { t{x: #a, y: #b} }

Named Fields

While the type declarations described above are suitable for most purposes, it is sometimes useful to be able to explicitly name the components of a constructor. So there is an alternative syntax for a constructor within a typedef as follows:

typedef named_list(#t) { nl{ name: list(char), list: list(#t) } | ... }

This form of constructor with curly braces instead of round braces and tags identifying each component can be freely mixed with the other style in a single typedef. Being able to name the fields means you don't have to add explicit wildcards for the components you aren't interested in when pattern matching:

fn printName (nl{ name: x }) { print(x) }

The downside of this type of constructor is that they cannot be curried as normal constructors can.

x = nl{ name: "mine", list: [1, 2, 3] }; // all fields must be supplied.

Aliases

There exists a very primitive aliasing system for types, basically

alias <name> = <type>;

so for example the string alias mentioned earlier is defined in the preamble as

alias string = list(char);

Really the aliasing system was only defined to support that single use-case, you can't currently even access aliases defined in another namespace. I may extend it later to allow that, and to take arguments.

Typeof

Alongside typedef there is a typeof operator that takes an expression and returns a string representation of its type. This is primarily used for internal testing but is also useful when debugging F♮ programs.

Next: Print