-
Notifications
You must be signed in to change notification settings - Fork 54
Type classes
So far we have seen examples of parametric polymorphism. When a predicate or function has a type variable in its type signature, it is possible to substitute any type for that type variable so the predicate or function must work for all possible types. It is not possible to do type-specific things with variables of that type, short of performing dynamic type checks.
Sometimes you need a predicate or function to work with multiple types or an open-ended set of types, but not all types. To that end, Mercury supports constrained polymorphism through type classes.
A "type class" is a name for a set of types for which certain predicates and/or functions, the "methods" of that type class, are defined. (You can liken them to abstract base classes or interfaces in object-oriented programming languages, if that helps.)
Let us declare a type class for the set of types representing simple geometric shapes.
:- typeclass shape(T) where [].A type class declaration declares the name of the type class (shape),
the type class parameters (T), and a list of methods after the where
keyword. There are restrictions on type class parameters which we will
explain later. The shape type class has an empty list of methods
for now.
Now we can declare some instances of the type class. It is possible to declare type class instances anywhere we have visibility of the type class declaration.
:- type point
---> point(float, float).
:- type rectangle
---> rectangle(point, float, float). % centre, width, height
:- type circle
---> circle(point, float). % centre, radius
:- instance shape(rectangle) where [].
:- instance shape(circle) where [].The two instance declarations declare rectangle and circle to be
instances of the shape type class. Each type class instance must
implement all the methods declared in the type class in the list
followed the where keyword. There are no methods to implement yet.
Instance declarations may only appear in the implementation section of a module (except for abstract instance declarations, introduced later).
The purpose of type classes in Mercury is to support constrained polymorphism. Let's see that in action.
:- pred shapes_only(T) <= shape(T).
:- mode shapes_only(in) is det.
% alternatively
:- pred shapes_only(T::in) is det <= shape(T).A predicate or function type may include type class constraints written
in the form <= TYPECLASS(TYPE, ...). The shape(T) constraint means
that shapes_only can only be called if the type variable T is bound
to a type that is an instance of the shape type class.
If a predicate or function requires multiple type class constraints then
you must write them together after a single <= symbol:
:- pred shapes_only2(T1, T2) <= (shape(T1), shape(T2)).We can define a couple of simple operations on shapes. For variety, we'll add one as a function method and the other as a predicate method in the type class declaration:
:- typeclass shape(T) where [
func get_centre(T) = point,
pred get_area(T, float),
mode get_area(in, out) is det
].The method list in a typeclass declaration can contain a list of pred,
func, and mode declarations, similar to how they would appear at the
module level except that they are separated by commas and do not begin
with the :- symbol.
Now all instances of the shape type class must implement the two new
methods. The first way to implement methods is to write the clauses
directly in an instance declaration, as so:
:- instance shape(rectangle) where [
get_centre(rectangle(Centre, _Width, _Height)) = Centre,
( get_area(Rect, Area) :-
Rect = rectangle(_Centre, Width, Height),
Area = Width * Height
)
].The method clauses are separated with commas, as usual for elements of
a list. Notice also how we parenthesise the second clause so that the
conjunction operator (,) in the body of the predicate is not confused
for a comma separating clauses. We could have parenthesised the body of
the predicate instead.
The second way to define methods is by giving the name of a predicate or function that implements the method, like so:
:- instance shape(circle) where [
func(get_centre/1) is circle_centre,
pred(get_area/2) is circle_area
].
:- func circle_centre(circle) = point.
circle_centre(circle(Centre, _Radius)) = Centre.
:- pred circle_area(circle, float).
:- mode circle_area(in, out) is det.
circle_area(circle(_Centre, Radius), Area) :-
Area = math.pi * Radius * Radius.An entry func(METHODNAME/ARITY) is FUNCNAME or pred(METHODNAME/ARITY) is PREDNAME in the method list states that the given function method or
predicate method in the type class is implemented by the named function
or predicate respectively. The func(...) and pred(...) syntax
distinguishes function and predicate methods with the same name and
arity.
We can call a method just like a predicate or function. The argument types (and return type, if applicable) of the call must have been constrained to be a member of that method's type class, or which match one of the instance declarations visible at the point of the call.
This predicate uses methods of the shape type class to get information
about a shape without knowing its exact type, then print it out:
:- pred print_shape(T, io, io) <= shape(T).
:- mode print_shape(in, di, uo) is det.
print_shape(Shape, !IO) :-
point(X, Y) = get_centre(Shape),
get_area(Shape, Area),
io.format("Shape centred at (%f, %f) with area %f.\n",
[f(X), f(Y), f(Area)], !IO).The calls to get_centre and get_area are possible because the
first argument of each call, Shape, has type T which has been
constrained to be a member of the type class shape
in the type signature of print_shape.
Without that constraint, T could be bound to any arbitrary type
so the method calls would be invalid.
It's possible to abstractly export type classes and type class instances in a module's interface section.
An abstract type class declaration defines the name of a type class,
but does not define what methods must be implemented for instances of the
type class. They have the same form as a normal typeclass declaration but
without the where [...] part, and are only useful in the interface
section of a module. Each abstract type class declaration must be
accompanied by a corresponding non-abstract type class declaration.
Similarly, an abstract instance declaration declares an instance of a particular type class without defining how the type class methods are implemented. Abstract instance declarations are only useful in the interface section of a module and must be accompanied by a corresponding non-abstract instance declaration.
Then, a module can import an abstract type class declaration and know that the type class exists but not declare new instances of the type class. Similarly, a module can import an abstract instance declaration and know that the instance of that type class exists, but not be able to directly call methods of that type class.
The following module exports a predicate mix/3 whose first argument
can be either an int or string. No other modules can declare more
hashable instances, and no other modules can see or call the internal
hash method.
:- module abstract_tc.
:- interface.
:- import_module int, string.
:- typeclass hashable(T). % abstract type class declaration
:- instance hashable(int). % abstract instance declaration
:- instance hashable(string). % abstract instance declaration
:- pred mix(T, int, int) <= hashable(T).
:- mode mix(in, in, out) is det.
:- implementation.
:- typeclass hashable(T) where [
func hash(T) = int
].
:- instance hashable(int) where [
hash(X) = X
].
:- instance hashable(string) where [
func(hash/1) is string.hash
].
mix(X, H0, H) :-
H = H0 `xor` hash(X). % Just a bad example.
:- end_module abstract_tc.Consider if one module declared a type class instance tc(list(T)) and
then another module declared an instance tc(list(int)). A call to a
method in that type class would be ambiguous for the type list(int).
Would the method call resolve to the first instance or the second
instance?
We don't want that situation to arise so there are restrictions on type class parameters to prevent overlapping type class instances. The restrictions are given in the reference manual:
An 'instance' declaration gives a type for each parameter of the type class. Each of these types must be either a type with no arguments, or a polymorphic type whose arguments are all type variables. For example 'int', 'list(T)', 'bintree(K, V)' and 'bintree(T, T)' are allowed, but 'T' and 'list(int)' are not. The types in an instance declaration must not be abstract types which are elsewhere defined as equivalence types. A program may not contain more than one instance declaration for a particular type (or sequence of types, in the case of a multi-parameter type class) and typeclass. These restrictions ensure that there are no overlapping instance declarations, i.e. for each typeclass there is at most one instance declaration that may be applied to any type (or sequence of types).
Unfortunately, these restrictions are part of the reason working with type classes can be awkward in practice. Sometimes it is possible to work around the restrictions with creative uses of wrapper types. (My understanding is that some of the restrictions could be be relaxed, with effort.)
By the way, duplicate type class instances across different modules (being a trivial case of overlapping instances) are prevented at link time: duplicate instances will generate the same symbol name in different object files which, when combined into a program, should result in a link error. This does not work with the Java and C# back-ends, and does not always work with the C back-end depending on linker behaviour.
We previously said that <= introduces type class constraints.
More specifically, they introduce universal type class constraints.
Universal type class constraints must be satisfied by the caller of a
predicate or function.
The other type of type class constraints are existential type class
constraints, introduced with the => operator, that must be satisfied
by the callee. Existential type class constraints can only constrain
explicitly existentially quantified type variables
(see Existential types).
A predicate or function declaration may have both universal and existential constraints; existential constraints must precede the universal constraints.
We could declare predicate that parses a string and returns a shape of some type like this:
:- some [T] pred parse_shape(string, T) => shape(T).
:- mode parse_shape(in, out) is semidet.If a call parse_shape(String, Shape) succeeds then Shape must be
bound to a value of some type that is an instance of the shape type
class.
Existential type class constraints can also be applied to existentially quantified type variables in discriminated union types.
Suppose we want a discriminated union of shapes and colors, where the set of shape types is open-ended. We can define such a type like this:
:- type shape_or_color
---> some [T] shape(T) => shape(T)
; color(color).The type class constraint prevents the construction of a
term with the shape constructor
unless its argument is an instance of the shape type class. When the
argument is taken out it will be known to be an instance of the shape
type class, so we can call the methods of that type class and so on.
This was a brief introduction to type classes. Please see the reference manual for details. We also did not cover these topics at all:
- Type class constraints on type class declarations
- Type class constraints on instance declarations
- Functional dependencies
:- module typeclass_example.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is det.
:- implementation.
:- import_module float.
:- import_module list.
:- import_module math.
:- import_module string.
:- typeclass shape(T) where [
func get_centre(T) = point,
pred get_area(T, float),
mode get_area(in, out) is det
].
:- type point
---> point(float, float).
:- type rectangle
---> rectangle(point, float, float). % centre, width, height
:- type circle
---> circle(point, float). % centre, radius
:- instance shape(rectangle) where [
get_centre(rectangle(Centre, _Width, _Height)) = Centre,
( get_area(Rect, Area) :-
Rect = rectangle(_Centre, Width, Height),
Area = Width * Height
)
].
:- instance shape(circle) where [
func(get_centre/1) is circle_centre,
pred(get_area/2) is circle_area
].
:- func circle_centre(circle) = point.
circle_centre(circle(Centre, _Radius)) = Centre.
:- pred circle_area(circle, float).
:- mode circle_area(in, out) is det.
circle_area(circle(_Centre, Radius), Area) :-
Area = math.pi * Radius * Radius.
main(!IO) :-
print_shape(circle(point(1.0, 2.0), 3.0), !IO),
print_shape(rectangle(point(4.0, 5.0), 6.0, 7.0), !IO).
:- pred print_shape(T, io, io) <= shape(T).
:- mode print_shape(in, di, uo) is det.
print_shape(Shape, !IO) :-
point(X, Y) = get_centre(Shape),
get_area(Shape, Area),
io.format("shape centred at (%f, %f) with area %f\n",
[f(X), f(Y), f(Area)], !IO).