This is just a quick post, crystallizing some of the ideas I’ve had recently about organizing numeric classes in Haskell.

These classes are the usual way of overloading the familiar arithmetic operators (+, -, * and their buddies) for various types. Personally, I think that they could benefit from a bit of spring cleaning.

Haskell’s Hierarchy

Here’s an overview of Haskell’s hierarchy of typeclasses:

You can see the different typeclasses involved, and the dependencies linking all of them together.

Eq

The first class is Eq, giving us decideable equality for a type:

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

Naturally, this defines the == operator we all know and love. This must be an equivalence relation, satisfying:

x == x
x == y -> y == x
x == y, y = z -> x = z

Ord

Then you have Ord, which augments Eq with comparisons:

class Eq a => Ord a where
  compare :: a -> a -> Ordering

(I’ve simplified things a bit here)

And the Ordering type is a simple enumeration:

data Ordering = LT | EQ | GT

It’s clear that Ord should entail Eq, since we can just check whether compare returns EQ for equality.

Using compare, the standard comparison operators <, >, <=, >= can all be provided. While Ord doesn’t specify any laws itself, it’s common to assume that <= is a partial order, satisfying:

x <= x
x <= y, y <= z -> x <= z

Semigroup

Now we get to the “algebraic” classes.

The first of these is Semigroup:

class Semigroup a where
  (<>) :: a -> a -> a

The only thing we assume about this operator is its associtivity:

a <> (b <> c) = (a <> b) <> c

Monoid

Monoid augments the Semigroup class with an identity element:

class Semigroup  a => Monoid a where
  mempty :: a

This element satisfies:

x <> mempty = x
mempty <> x = x

Enum

Next, we have the Enum class:

class Enum a where
  toEnum :: Int -> a
  fromEnum :: a -> Int

The main purpose of this class is to provide semantics for the [a..b] syntax. Otherwise, this is more of a pragmatic class, instead of one with some underlying algebraic idea.

Num

And now we have the infamous Num class:

class Num a where
  (+) :: a -> a -> a
  (*) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a

This is a big amalgamation of everything you’d expect numbers to be, and then some more. The main purpose of this is to interpret the operators mentioned here, including - as well, and to interpret numeric literals, like 3, or 420, using the fromInteger method.

In my opinion, this class is pretty ugly, and perhaps my central motivation in wanting to think about some ways to reform this hierarchy.

Real

Now, you have another ad-hoc class, called Real:

class (Num a, Ord a) => Real a where
  toRational :: a -> Rational

I confess that I’ve never used this class all that much. Ostensibly, its purpose is just to provide a means to convert some type into rational numbers, which provides a direct means for comparision, hence the Ord instance.

If we can think of elements of a type as being rational numbers, it’d make sense to also stipulate that they’re numbers, using the inferred operations. The Num requirement makes sense, under this interpretation.

Integral

Finally, we have the Integral class:

class (Real a, Enum a) => Integral a where
  quotRem :: a -> a -> (a, a)
  toInteger :: a -> Integer

(Simplifying a bit here, but these form a complete definition).

Basically, this is for types that are equivalent to integers, and we have the corresponding division operations we expect to have for integers: mod, div et alii.

Interlude: Two Worlds

So far, we’ve seen a basic overview of the numeric hierarchy. For the most part, it gets the job done. We can calculate useful things, while also being somewhat generic over the numeric types we use. This allows Haskell to have a principled approach towards providing standard arithmetic for the various integer types, like Word, Int, Int64, etc.

That being said, I think there are a few thorns with the organization of these classes. Analyzing the structure of the hierarchy a bit more can help illuminate these issues.

The Mathematical Classes

There are a few classes that are inspired by Math. For example, Semigroup and Monoid are chiefly mathematical concepts. Formally, a Semigroup is a set $S$ equipped with an operation $\cdot$, satisfying:

$$ x \cdot (y \cdot z) = (x \cdot y) \cdot z $$

A Monoid is a Semigroup with an element $e$, serving as the identity element:

$$ \begin{aligned} x \cdot e &= x \cr e \cdot x &= x \end{aligned} $$

The Eq class is also inspired by Math. The == operator is modeled over an Equivalence Relation, which is really just a mathematical definition of the familiar notion of equality.

While Ord, technically speaking, doesn’t specify any laws, we can model the Ord typeclass after a Partial Order. This is a set $S$, equipped with a relation $\leq$, satisfying:

$$ \begin{aligned} &x \leq x \cr &x \leq y, y \leq z \implies x \leq z \end{aligned} $$

The common thread here is that each of these classes correspond to some kind of mathematical object, with corresponding laws.

The Pragmatic Classes

The remaining classes we’ve seen are more loosely defined, and fall into what I call the “pragmatic classes”. The chief example here is Num. These classes, as I see them, are about defining useful operations, caring more about having a vector to provide operators, over representing some kind of principled abstraction.

Very often, these are conceived of as providing a general class of types that “behave like” some other concrete type. For example, Real represents types that are essentially like the Rational type.

The disadvantage in this kind of class is that the operations involved are often lawless, and sometimes instances have to cheat. Many Num instances have to bend some of the rules a bit, since not all operations make sense for that type. This happens because the Num abstraction is an ad-hoc generalization of the well-known integer type, and not a more principled collection of operations and laws.

A Proposed Hierarchy

I don’t think I’ve found the perfect solution to making a hierarchy of numerical classes, nor do I think such a solution can be found, but I do have a few ideas on making things a bit better.

Here’s an alternative hierarchy of classes:

Semigroup, Monoid

These are the same classes that we’re used to, inspired by the same mathematical objects:

class Semigroup a where
  (<>) :: a -> a -> a

class Semigroup a => Monoid a where
  mempty :: a

Group

Mathematically, a Group is a Monoid, where each element $a$ has an inverse $a^{-1}$, satisfying:

$$ a \cdot a^{-1} = e = a^{-1} \cdot a $$

This leads to the following type-class:

class Monoid a => Group a where
  negate :: a -> a

Additive

Mathematically, this models an Abelian Group, which is just a group, but where the group operation is commutative, i.e.:

$$ a \cdot b = b \cdot a $$

It’s common to use $+$ for the group operation instead.

This gives us the following typeclass:

class Group a => Additive a where
  (+) :: a -> a -> a

This class serves to introduce the + operator, which has to be commutative. The additional rule is that + and <> have to coincide.

We can also define:

(-) :: Additive a => a -> a -> a
a - b = a + negate b

Ring

Mathematically, a Ring is an Abelian Group, equipped with multiplication as well, satisfying:

$$ a(b + c) = ab + ac (b + c)a = ba + ca 1a = a = a1 $$

This gives us the following typeclass:

class Additive a => Ring a where
  (*) :: a -> a -> a
  one :: a

satisfying the associated laws.

Choosing Instances

Given some Ring, we have a Monoid instance, matching up with addition +. We might also want to use multiplication instead, leading us to define the following wrapper:

newtype Multiply m = Multiply m

instance Ring m => Semigroup (Multiply m) where
  (<>) = (*)

instance Ring m => Monoid (Multiply m) where
  mempty = one

We can use this wrapper to select the right version of Monoid, which is useful.

Num

Now we move on from the nice mathematical classes, to the more pragamatic classes.

First, we have Num. Having already defined many ring operations, we’re left with just:

class Ring a => Num a where
  fromInteger :: Integer -> a

Note that we’ve taken the liberty of removing abs and signum, which aren’t particularly principled to begin with. If these are crucial, I would recommend either sticking them in the Integral class, or creating an extra class after Num, to contain them.

We use the Num class to interpret numeric literals.

Enum

This remains unchanged, although now we have an Ord requirement. This makes sense in my view, since you can use the enumeration indices to compare two elements, and this always makes sense.

Real

For Real, the idea is unchanged. We have a class that represents the ability to convert to rational numbers.

Integral

This works the same way as it did previously, with conversions back to integers, and the corresponding division operations defined therein.

Roundtripping

Given that Integral implies Num, it might be a good idea to add an additional law, specifying that the behavior of the newly added division operators can be derived through first converting to Integer, performing the operation there, and then converting back to the original type.

Conclusion

I’m not entirely satisfied with the tail end of the hierarchy, and I wonder if a better approach to the so-called “pragmatic classes” might exist.

Another big hole I’ve left is conversions that might possibly fail. For example, converting large integer types into smaller integer types.

That being said, I’m pretty happy with the algebraic side of things, and I really think that the addition of Groups would be quite useful, given how much love Monoids have seen so far.