109 lines
4.1 KiB
Markdown
109 lines
4.1 KiB
Markdown
|
+++
|
||
|
|
title = "Type classes and overloading"
|
||
|
|
weight = 1
|
||
|
|
+++
|
||
|
|
|
||
|
|
BH's `class` and `instance` mechanisms form a systematic way to do
|
||
|
|
*overloading* (the approach has been well tested in Haskell).
|
||
|
|
|
||
|
|
|
||
|
|
Overloading is a way to use a common name to refer to a set of
|
||
|
|
operations at different types. For example, we may want to use the "`<`"
|
||
|
|
operator name for the integer comparison operation, the floating-point
|
||
|
|
comparison operation, the vector comparison operation and the matrix
|
||
|
|
comparison operation. Note that this is not the same as polymorphism: a
|
||
|
|
polymorphic function is a *single* function that is meaningful at an
|
||
|
|
infinity of types (*i.e.,* at every possible instantiation of the type
|
||
|
|
variables in its type). An overloaded identifier, on the other hand,
|
||
|
|
usually uses a common name to refer to a (usually) small set of distinct
|
||
|
|
operations.
|
||
|
|
|
||
|
|
|
||
|
|
Further, it may make sense to have "`<=`", "`>`" and "`>=`" operations
|
||
|
|
wherever there is a "`<`" operation, on integers, floating points
|
||
|
|
numbers, vectors and matrices. Rather than handle these separately, we
|
||
|
|
say:
|
||
|
|
|
||
|
|
|
||
|
|
- there is class of types which we will call `Ord` (for "ordered types"),
|
||
|
|
- that the integer, floating point, vector and matrix types are members
|
||
|
|
(or "instances") of this class, and
|
||
|
|
- that all types that are members of this class have appropriate
|
||
|
|
definitions for the "`<`", "`<=`", "`>`" and "`>=`" operations. We also
|
||
|
|
say that these operations are *overloaded* across these instance types,
|
||
|
|
and we refer to these operations as the *methods* of this class.
|
||
|
|
|
||
|
|
|
||
|
|
Another example: we could use a class `Hashable` with an operation
|
||
|
|
called `hash` to represent those types $T$ for which we can and do
|
||
|
|
define a hashing function. Each such type $T$ has to specify how to
|
||
|
|
compute the `hash` function at that type.
|
||
|
|
|
||
|
|
|
||
|
|
Classes, and the membership of a type in a class, do not come into
|
||
|
|
existence by magic. Every class is created explicitly using a class
|
||
|
|
declaration, described in section
|
||
|
|
[4.5](fixme).
|
||
|
|
A type must explicitly be made an instance of a class and the
|
||
|
|
corresponding class methods have to be provided explicitly; this is
|
||
|
|
described in [4.6](fixme).
|
||
|
|
|
||
|
|
|
||
|
|
### Context-qualified types
|
||
|
|
|
||
|
|
|
||
|
|
Consider the following type declaration:
|
||
|
|
|
||
|
|
```hs
|
||
|
|
sort :: (Ord a) => List a -> List a
|
||
|
|
```
|
||
|
|
|
||
|
|
|
||
|
|
It expresses the idea that a sorting function takes an (unsorted) input
|
||
|
|
list of items and produces a (sorted) output list of items, but it is
|
||
|
|
only meaningful for those types of items ("`a`") for which the ordering
|
||
|
|
functions (such as "`<`") are defined. Thus, it is ok to apply `sort` to
|
||
|
|
lists of `Integer`'s or lists of `Bool`'s, because those types are
|
||
|
|
instances of `Ord`, but it is not ok to apply `sort` to a list of, say,
|
||
|
|
`Counter`'s (assuming `Counter` is not an instance of the `Ord` class).
|
||
|
|
|
||
|
|
|
||
|
|
In the type of `sort` above, the part before "`=>`" is called a
|
||
|
|
*context*. A context expresses constraints on one or more type
|
||
|
|
variables--- in the above example, the constraint is that any actual
|
||
|
|
type "`a`" must be an instance of the `Ord` class.
|
||
|
|
|
||
|
|
|
||
|
|
A context-qualified type has the following grammar:
|
||
|
|
|
||
|
|
```
|
||
|
|
ctxType ::= [ context => ] type
|
||
|
|
context ::= ( {classId { varId }, })
|
||
|
|
classId ::= conId
|
||
|
|
```
|
||
|
|
|
||
|
|
In the above example, the class `Ord` had only one type parameter
|
||
|
|
(*i.e.,* it constrains a single type) but, in general, a type class can
|
||
|
|
have multiple type parameters. For example, in BH we frequently use the
|
||
|
|
class "`Bits a n`" which constrains the type represented by `a` to be
|
||
|
|
representable in bit strings of length represented by the type `n`.
|
||
|
|
|
||
|
|
|
||
|
|
> **NOTE:**
|
||
|
|
>
|
||
|
|
> When using an overloaded identifier `x` there is always a question of
|
||
|
|
> whether or not there is enough type information available to the
|
||
|
|
> compiler to determine which of the overloaded `x`'s you mean. For
|
||
|
|
> example, if `read` is an overloaded function that takes strings to
|
||
|
|
> integers or Booleans, and `show` is an overloaded function that takes
|
||
|
|
> integers or Booleans to strings, then the expression `show (read s)` is
|
||
|
|
> ambiguous--- is the thing to be read an integer or a Boolean?
|
||
|
|
>
|
||
|
|
> In such ambiguous situations, the compiler will so notify you, and you
|
||
|
|
> may need to give it a little help by inserting an explicit type
|
||
|
|
> signature, e.g.,
|
||
|
|
>
|
||
|
|
> ```hs
|
||
|
|
> show ((read s) :: Bool)
|
||
|
|
> ```
|