What is the type of [1,2,3]? It is a list, containing Integers. What about [true, true]? Again a list, but it contains Booleans instead. It would be very cumbersome to have separate types such as IntegerList and BooleanList for each of these possibilities, and in fact infinitely many such types are possible. What we would like instead is one List type, with a parameter which gives us the types contained in the list.

Such a type is called a parametric, or generic, type. It contains two parts: a type operator, such as List, followed by a sequence of paramemters enclosed in brackets [...]. For example, [1,2,3] :: List[Integer], and [true,true] :: List[Boolean].

Lists are not the only parametric type. The standard library includes other parametric types, such as Option, Buffer, and Cell. Type operators, such as List, are declared using the same type declarations as any other type. For example, the declaration

type Buffer = orc.lib.state.types.BufferType

is part of the standard library; it declares the Buffer type operator.

How do we write functions that use parametric types? Consider the following definition of the append function, which appends two lists:

def append[T](List[T], List[T]) :: List[T]
def append([], l) = l
def append(h::t, l) = h::append(t,l)

The function append has a type argument, T, in its signature. The type T is the type of elements in the lists that we are appending. Notice that both argument lists must contain the same type of elements. The resulting list contains elements of that same type.

When calling the append function, in addition to providing its normal arguments, we must also provide its type argument:

append[Integer]([1,2,3], [4,5])

However, it would be very burdensome and verbose to provide type arguments to all such calls. Fortunately, in most cases, the type checker can infer the correct type arguments, in the same way that it infers the correct type for many expressions without any additional information. So in this case, we can simply write:

append([1,2,3], [4,5])

and the typechecker infers that the parameter T is Integer, since both argument lists are of type List[Integer]. For a more thorough explanation of how this inference occurs, please refer to Pierce and Turner's paper.

Inference of type arguments will always fail on certain kinds of calls, because the typechecker does not have enough information to infer the correct type. The most common case is a site call which constructs a parametric type without taking any arguments. For example:

val b = Buffer()

will never typecheck, since there is no way for the typechecker to know what type of elements the buffer should contain. In other languages such as ML, the typechecker might be able to infer this information from the rest of the program, but Orc's typechecker is based on local type inference, which must find the information locally, such as from the types of the arguments. So, to construct a buffer that will contain Numbers, a type parameter must be given:

val b = Buffer[Number]()

A type alias may have type parameters. For example, here is a type alias for triples:

type Triple[T] = (T,T,T)

Triple is now a type operator that takes one parameter. Any occurrence of Triple[T] is equivalent to (T,T,T).

Datatypes can also have type parameters. This allows a programmer to define very useful generic data structures. For example, this is necessary to define a reasonable datatype for trees:

type Tree[T] = Node(Tree[T], Tree[T], T) | Leaf()

Notice that the datatype is recursive, and the type parameter T is passed recursively to Tree to define the type of the subtrees.