3.1 Type classes

The class and instance is the primary organisation tool for Felix libraries that allow easy use and extension. The notion is taken from Haskell, generalised to support multiple type variables as in GHC.

Here is a simple typeclass and instance:

  class X[T] {
    virtual fun f: T -> T;
    fun g(x:T)=> f (f x);
  }
  
  instance X[int] {
    fun f(x:int)=> x + 1;
  }
  
  open X[int];
  
  println$ g 1;

In this code virtual functions are ones which may be overridden in instances. virtual functions may have definitions, which are used in any instance which does not define an override. Non-virtual functions cannot be overriden: instead they're dependent on the virtual functions only.

We define an instance of X for type int and then call the non-virtual function g for specialisation T -> int, which in turn calls f for that specialisation too.

Finally we open the typeclass for the specialisation T -> int. In effect this just makes f of (int) and g of (int) available.

3.1.1 Orders

We will cite one of the most important typeclasses in Felix:

std/algebra/equiv.flx

  NO FILE std/algebra/equiv.flx FOUND IN list()

std/algebra/partialorder.flx

  NO FILE std/algebra/partialorder.flx FOUND IN list()

std/algebra/totalorder.flx

  NO FILE std/algebra/totalorder.flx FOUND IN list()

This library file defines the concept of equality, total ordering, and the core operations of integral kinds: increment and decrement.

The code shows clearly the use of axioms to express semantics, for example we see equality must be an equivalence relation (reflexive, symmetric and transitive).

Also we note that the total order concept is derived from equality concept. When you open a Tord you get the methods of Eq as well.

3.1.2 Relation to C++

Type classes actually exist in much the same form in C++. If you define a template class with all static functions, then those functions without definitions are Felix virtuals, those with definitions are either non-virtuals or virtuals with defaults (C++ doesn't distinguish these two cases).

In C++, an instance is just a partical or full specialisation of the class, which in turn may include some or all of the functions. It's acceptable in both C++ and Felix to leave out definitions for functions you do not use.

The principal difference between Felix and C++ is that the C++ type system cannot support type recursion and hence is effectively useless: you cannot make a combinatorial definition of a polymorphic linked list in C++, in Felix it is a one liner:

  union list[T] = | #Empty | Cons of T * list[T];

using Felix's built in tuple and union constructors. The equivalent templates are easy to define in C++: the problem is the list[T] at the end of the definition.