Types and type classes

The world seems to be divided up into things, but not all things are interchangable.

For example, if I am eating, I want what I am eating to be food, not paint, but if I am painting my attic, I want to be using paint, not food. In linguistics, we see that different formatives have different distributions; phrases like john, the king of France, and Matilda das Stachelschwein share aspects of their distribution, whereas phrases like of, between the river and the barn, and run quickly behave quite differently. Similarly, sounds like b and p have something in common to the exclusion of t and e. Our grammatical operations are stated in terms of these similarity classes; we say that a construction requires an NP, or that voice dissimilation must happen after a bilabial plosive. However, which NP, or which bilabial plosive appears is irrelevant (for the purposes of that rule). In semantics, in contrast to (some theories of) syntax, morphology, and phonology, we have an infinity of such similarity classes, which are called (semantic) types. In particular, we have objects, functions over objects, functions over functions over objects, and so on. The different types are described inductively, that is, by means of a recipe. We are given a (finite) set of basic types. In semantics, these might be e (for the type of entities), t (for the type of truth values), v (for the type of events), i (for the type of times or temporal indices), w (for the type of possible worlds), etc. In this class we will stick with e and t (for entities and truth values). Given any two types, α and β, we construct a new type, written \(\alpha \rightarrow \beta\), which we interpret as the type of functions which take objects of type α as their inputs and produce objects of type β.

In Haskell, there are some basic types, such as Int (the type of machine integers, with values between -9223372036854775808 and 9223372036854775807), Char (the type of unicode characters), Bool (the type of truth values), () (the ‘unit’ type, with exactly one defined inhabitant, also written ()). The type of functions between types a and b is written a -> b (which you’ve gotta admit is pretty close to \(a \rightarrow b\)). In Haskell, however, one can define additional basic types, and type constructors.

A type might have some relevant structure. In fact, multiple types might share the same structure. The notion of a type having a structure is expressed in Haskell by means of type classes. Some type classes are rather banal; the type class Show expresses that each element of a particular type can be turned into a String.¹

class Show a where
  show :: a -> String

This type class definition should be read in the following way:

• there is a type class called Show
• if a type a belongs to this class,
• then there is a function show defined on elements of type a, which turns these elements into strings.

The type class Bounded expresses that a particular type has two special elements, called the minBound and the maxBound.²

class Bounded a where
  minBound :: a
  maxBound :: a

This type class definition should be read in the following way:

• there is a type class called Bounded
• if a type a belongs to this class,
• then there is an element minBound of this type
• and an element maxBound of this type.

A more useful type class, Eq, expresses that we know how to compare two elements of a type to determine whether they are equal.

class Eq a where
  (==) :: a -> a -> Bool

This type class definition should be read in the following way:

• there is a type class called Eq
• if a type a belongs to this class,
• then there is a function == which takes two elements of this type, and returns True or False.

Not all types can be compared for equality. For example, how should we test whether two functions f and g of some type are equal?! It is not even clear what this should mean! For example, are the functions \(f(x) = (x + 1)^{2}\) and \(g(x) = x^{2} + 2x + 1\) equal or not? If we take these functions ‘literally’ as instructions for computing a value, \(f\) performs two operations (adding one, and squaring the result), while \(g\) performs four (squaring, doubling, and two additions). A useful notion is extensional equality, which means that they give the same results on the same inputs, irrespective of how they compute these results. In general we cannot determine whether two functions are extensionally equal, but, if the type a of inputs to the functions is structured in a particular way, we can:

instance (Bounded a, Enum a, Eq b) => Eq (a -> b) where
  f == g = all sameOutput possibleInputs
    where
      sameOutput x = f x == g x
      possibleInputs = [minBound .. maxBound]

Here we have stated how to compare two functions for equality, PROVIDED THAT we know how to

1. compare their outputs for equality
2. enumerate their possible inputs

We state these provisos by listing constraints on the allowable types (to the left of the =>). Here, constraining the result type b of the functions to be one where equality is decidable is straightforward. To constrain a so that we can enumerate it, we require that it be bounded, so that we know where to start enumerating from, and that it be enumerable, so that we can do the enumerating.

The expression [minBound..maxBound] makes use of three linguistic idioms associated with typeclasses: the minBound and maxBound are from the Bounded typeclass, and the [..] is from the Enum typeclass. This expression cannot be evaluated on its own, but requires that we specify which type we are intending to use. Another way of thinking about expressions like [minBound..maxBound] is that they are simply linguistic terms, which must be interpreted. They can be interpreted in any type which instantiates both the Enum and the Bounded typeclasses.

Some examples follow:

> [minBound..maxBound] :: [()]
> [()]
>
> [minBound..maxBound] :: [Bool]
> [False,True]
>
> [minBound..maxBound] :: [Int]
> [-9223372036854775808,-9223372036854775807,...,9223372036854775806,9223372036854775807]

In general, we can create terms using operations from multiple diverse typeclasses (as illustrated above with the Enum and Bounded typeclasses). In order to interpret such terms in some type, we need to (independently!) specify how to interpret each typeclass in that type. This permits us to focus on interpreting individual typeclasses, and to automatically obtain a way to interpret their combination. (This is a modular approach to program construction.)