# Samuel Evans-Powell

## Haskell & Category Theory

*I've been learning about Haskell and Category Theory lately. In this*
*series of posts I hope to collect my thoughts. Please pop me an email or open a*
*pull request here if you want to make any suggestions/corrections, I'm still*
*learning myself.*

### Abstraction

Software developers do alot of abstraction. When we "abstract", we make a
conscious decision to magnifiy the similarities between "things" and ignore
their differences. In doing so we create "abstractions": interfaces that take
advantage of common patterns of *form* and *behaviour* in our code, allowing us
to think about our programs at a higher level. A car provides us a with a simple
interface (pedals, steering wheel) to operate a very complex machine. As
drivers, we (usually) don't have to worry about the internals of our car, we
merely operate the interface. This is an example of abstraction.

As programmers we build abstractions for files, memory, HTTP requests, web forms, etc. Wouldn't it be nice if we had a field of mathematics (and the years of research that entails) to aid us in identifying abstractions? That could provide a solid foundation for us to build our programs on?

It turns out that we do: Category Theory. For a good definition of Category
Theory see ^{1} and ^{2}, but essentially Category Theory is a field concerned
with structure, composition and identity. Category Theory provides a formal
basis for abstractions like Monoid, Functor, Applicative and Monad.

I find Category Theory exciting because it provides a more principled source of abstractions and ideas for programmers to build their programs upon. The nice thing about using an established field of mathematics is that the abstractions identified by Category Theory are usually very general and stable, which encourages the creation of general and re-usable code: a much desired property.

Bartosz Milewski has a great series called *Category Theory for Programmers*

### Type classes

Type classes can be thought of as Haskell's version of the interfaces in other languages. This is not strictly true, but is good enough to serve as our intuition: a set of functions with no implementation (or a default implementation) that data types must implement to be considered an instance.

Type classes allow us to express common, repeated patterns in our code and to, in future, treat many different data types according to a common interface.

### Monoid

One example of a type class from Category Theory is the Monoid type class (*):

class Monoid a where mempty :: a mappend :: a -> a -> a

Monoid is used to categorize data types that have a binary operation, and a value that acts a neutral element in that operation. Pretty abstract isn't it? When approaching category theory, get used to thinking at this kind of abstract level. When writing C++, I tended to think too concretely to be able to identify these kind of patterns.

An example: integers form a monoid under multiplication. Multiplication is the binary operation:

3 * 3 = 9

and the integer '1' is the neutral element, as any integer `x`

multiplied by 1
gives us back `x`

:

3 * 1 = 3 -4 * 1 = -4 x * 1 = x

We can express this in Haskell by declaring Integer to be an instance of Monoid:

instance Monoid Integer where mempty :: Integer mempty = 1 mappend :: Integer -> Integer -> Integer mappend = (*)

Note that integers also form a monoid under addition. Because there can only be one instance of a type class for a given type, Haskell wraps Integers into 'Sum' and 'Product' types, the first forming a Monoid under addition and the second under multiplication. Don't worry about this too much.

Many other things form a Monoid. For example, lists form a Monoid under concatenation (++). The empty list ([]) acts as the neutral element in this operation.

Now that we've defined a Monoid instance for our Integers, we can use them wherever we can use a Monoid. There is a wealth of standard library functions that deal with Monoids and this is part of the power of type classes.

The next step is to try and identify these structures within your codebase. If a
particular function is only making use of the equivalent of `mempty`

and
`mappend`

, it can be generalized to act on Monoids.

### Notes

- The Monoid type class has a third function (mconcat) but it can be derived from the first two functions (source).

### References

^{1}

B. Milewski, "Category Theory for Programmers", Bartosz Milewski's Programming Cafe, 2014. [Online]. Available: https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/. [Accessed: 01- Feb- 2018].

^{2}

B. Milewski, Category Theory. 2016. Available: https://www.youtube.com/playlist?list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_.