Type Notation

The type notation used occasionally in this wiki is quite simple to understand.

Assume we have a function:

fn add(x, y) {
    x + y
}

It's type is:

int -> int -> int

The -> is the function operator, and it is right-associative, so that parses as:

int -> (int -> int)

The lhs is the argument type to the function, and the rhs is the output type of the function.

Now you might be wondering "shouldn't it be (int, int) -> int then?" Well, in the Typed Lambda Calculus that this notation comes from, all functions take a single argument. A function that is notated with multiple arguments like add above can be converted to a function that takes one argument and produces a function that takes the second argument and produces the result, as if you had written:

fn add(x) {
    fn (y) { x + y }
}

Which is more obviously of type int -> int -> int. This language actually supports this, see Currying.

Generics

Type notation also supports type variables, allowing generic or polymorphic types. For example the standard function map has a type of (#a -> #b) -> list(#a) -> list(#b). Breaking that down, (#a -> #b), the first argument to map, is a function that takes some unspecified type #a and produces some other unspecified type #b. Given such an argument, map will return a function that accepts a list of that first type #a and produces a list of that second type #b. map does not care what types #a and #b are.