Chapter 4: Basic Typeclasses or “Show Me A Monoid”

The simplest case of a typeclass is a single-parameter typeclass that works on concrete types (as opposed to type functions such as Maybe a). Such typeclasses are similar to Java interfaces, but even the next kind of typeclass, described in the “Functor” section, which works on type functions (with type such as * -> *) rather than concrete types, does not exist in widespread imperative languages, making them much less concise and powerful than they could have been.

An easy example of typeclass is Show:

1 class Show a where
2     show :: a -> String

It basically defines a function show that takes a value of some type a :: * and converts it to String. If we take our type Person defined above, we can make it an instance of this typeclass as follows:

1 instance Show Person where
2     show (Person name age) = name ++ " is " ++ show age ++ " years old"

Notice how there is no implicit type conversions in haskell, so we cannot simply write ... ++ age ++, since age is of type Int, not String that operator ++ expects. Otherwise it’s pretty straightforward - you define function bodies for your types that you want to make a part of a certain typeclass, and these functions start working on your types.

Typeclass Show defines a useful (and straightforward) abstraction “how should a value of any type be represented as a string?”. In our type-theoretic notation from “Chapter 2M” Show would be represented as:

which basically says “it’s some type with the function show :: a -> String defined”.

Algebra is cool

Now let’s get more abstract and consider some type \(A:U\) - a bunch of objects with some similar properties grouped together. It can be Nat - natural numbers, or String, or Char or whatever else you may think of. Taken in itself it’s nothing more than than - a bunch of objects thrown together. We can’t really do anything with them, there is no structure. What if we add some to make things more interesting?

Let us define some binary operation \(\cdot\) for our type, i.e. a function that takes two members of our type and turns it into a third - \(\cdot : A \rightarrow A \rightarrow A\). It can be addition for Nat or integers, string concatenation for String, or operation of “having sex” for people, which tends to produce other people. A type with such a binary operation is called a Magma in algebra. Such an operation adds a certain structure to our type and makes it more interesting to work with - as now we can combine any two elements of our type and get a third one. If the abstraction of type describes pretty much everything we can think of, the abstraction of Magma is much more specific - not every type allows introduction of such an operation - but still general enough to describe both natural numbers as well as humanity. If we continue adding structure via additional operations, functions, and laws on them - we gradually get more and more specific.

The art of programming is finding the right level of abstraction for our model so that it is general enough to use concise and powerful abstractions, yet specific enough to be able to correctly describe all the objects in our model and relationships between them. You can code anything in JavaScript or any other language by being very specific - but it tends to be verbose, difficult to understand and maintain, and error-prone. If you use good abstractions in a strongly and statically typed language such as Haskell - your code will be concise, efficient, fast, and easy to maintain.

In type theory, Magma is defined as:

which says exactly what we described above - it’s a type \(A\) with a binary operation defined on it.

What if we want even more structure and require our \(\cdot\) operation to be associative, i.e. make sure that \(x \cdot (y \cdot z) = (x \cdot y) \cdot z\) for all \(x, y, z\)? We turn our Magma into Semigroup. It is easy to see that natural numbers with addition is a Semigroup, as well as String with string concatenation. However, people with operation “having sex” is definitely not a Semigroup and the equation itself is against the law in most of the countries. I think we’ve taken this analogy far enough.

Let us also add something that is called an identity element to our Semigroup type and we get a Monoid - type \(A\) with an associative binary operation and an identity element \(e\). For an identity element to be called that we require that \(x \cdot e = x\) as well as \(e \cdot x = x\). For natural numbers with addition an identity element is 0, for strings with concatenation - an empty string “”. What is the identity element for natural numbers with multiplication?

Monoids are a cool abstraction because it has an interesting structure, but at the same time they describe a lot of very different types in Haskell - not just all the numerical types and strings, but also any lists and some special kinds of computations.

Monoid can be defined as:

which summarizes everything we discussed above. But how do we define and use these cool \(\sum\)-types in Haskell?

Typeclasses Hierarchy in Haskell

In Haskell, we could define Monoid as follows:

1 class Monoid a where
2         e   :: a
3         (*) :: a -> a -> a

In reality, it is defined a bit differently, as typeclasses can extend each other - a very useful feature, since we can follow along our gradual structure build up in the same logic as described in the previous section. I.e., we could define a Magma, then extend it and get a Semigroup, then add an identity element and get a Monoid. As of this writing in the base haskell libraries, Monoid extends Semigroup roughly as follows:

 1 -- semigroup is simply a type with binary op
 2 class Semigroup a where
 3         (<>) :: a -> a -> a
 4 
 5 -- note the extension syntax when defining a Monoid:
 6 class Semigroup a => Monoid a where
 7 -- identity element
 8         mempty  :: a
 9 
10 -- mappend has a default implementation and equals operator (<>) from Semigroup
11 -- this is a legacy method and will be removed in the future, as (<>) is available
12         mappend :: a -> a -> a
13         mappend = (<>)
14 
15 -- mconcat is the list folding function we discussed above!
16         mconcat :: [a] -> a
17         mconcat = foldr mappend mempty

Here we notice several interesting things. First of all, there is unfortunately no way to put the mathematical Semigroup or Monoid laws in typeclass definition - Haskell has no way of enforcing or checking them. So, typeclasses can only define function type signatures and default implementations for these functions. However, it is extremely important to make sure your types follow relevant typeclass laws that are always mentioned in the typeclass documentation if you make your type an instance of a certain typeclass. The reason for this is that Haskell compiler (at least GHC) often uses these laws when running various optimizations - so if your type does not respect them, your code may start doing things which you do not expect.

Second, Monoid typeclass in Haskell has the mconcat function added with the default definition provided. This function folds a list of values of a monoidal type using its (<>) binary operation. The beauty of default definitions is that when you make your type an instance of Semigroup and then Monoid you only need to define the binary op (<>) and the identity element mempty. Once you’ve done that, you can safely apply mconcat to lists of your type and it will work “automagically”. As we will see down the road, a lot of more complex typeclasses provide many more methods with default definition, which makes a programmer’s life much easier - once you learn to use the typeclasses well. You can also provide your own definition for a default method if you think you can make it more efficient.

The other very powerful feature of typeclasses is that you can define instances for parametric types as well as concrete ones. E.g., you can make sure that a list of any type [a] is a Semigroup by defining the binary operation to be equal to list concatenation:

1 instance Semigroup [a] where 
2         (<>) = (++)

Once you have this definition (and it is a part of the base library), you can use operator (<>) for any lists - e.g., [1,2] <> [4,5] should produce [1,2,4,5] as a result. If you design a library or a complex enough project, it really pays to think through the typeclass structure and define as many “automagical” instances as makes sense to help you avoid boilerplate and make code more readable and maintanable.

Now that we have seen a glimpse of what basic typeclasses can do for us, let’s move on to typeclasses defined for the type functions or parametric types such as Maybe a or [a]. The first such typeclass, which we have “invented” in the end of Chapter 2 is Functor.