A group extension of an abelian group 
If you’re not a professional mathematician, then that is pure gobbledigook. But that seems to be typical of how initiates of category theory talk about it. But the basic concepts, while abstract, really aren’t all that tricky. In many ways, it feels a lot like set theory: there’s a simple conceptual framework, on which you can build extremely complicated formalisms. The difference is that while many people have spent years figuring out how to make the basics of set theory accessible to lay-people, but that effort hasn’t been applied to set theory.<\/p>\n
What\u2019s the point?<\/h2>\n
Ok, so why should you care about category theory?<\/p>\n
Category theory is a different way of thinking, and it’s a language for talking about abstractions. The heart of engineering is abstraction. We take problems, and turn them into abstract structures. We look at the structures we create, and recognize commonalities between those structures, and then we create new abstractions based on the commonalities. The hardest part of designing a good library is identifying the right abstractions.<\/p>\n
Category theory is a tool for talking about structures, which is particularly well suited to thinking about software. In category theory, we think in terms of arrows<\/em>, where arrows are mappings between objects. We’ll see what that means in detail later, but the gist of it is that one example of arrows mapping between objects is functions mapping between data types in a computer program.<\/p>\n Category theory is built on thinking with orrows, and building structures using arrows. It\u2019s about looking at mathematical constructions built with arrows, and in those structures, figuring out what the fundamental parts are. When we abstract enough, we can start to see that things that look very different are really just different realizations of the same underlying structure. Category theory gives us a language and a set of tools for doing that kind of abstraction – and then we can take the abstract structures that we identify, and turn them into code – into very generic libraries that express deep, fundamental structure.<\/p>\n We’ll get started by looking at a simple mathematical structure called a monoid, and how we can implement it in code; and then, we’ll move on to take an informal look at how it works in terms of categories.<\/p>\n Most of the categorical abstractions in Scala are implemented using something called a typeclass, so we’ll start by looking at typeclasses. Typeclasses aren’t a category theoretical notion, but they make it much, much easier to build categorical structures. And they do give us a bit of categorical flavor: a typeclass defines a kind of metatype – that is, a type of type – and we\u2019ll see, that kind of self-reflective abstraction is a key part of category theory.<\/p>\n The easiest way to think about typeclasses is that they’re a kind of metatype – literally, as the name suggests, they define classes where the elements of those classes are types. So a typeclass provides an interface that a type must provide in order to be an instance of the metatype. Just like you can implement an interface in a type by providing implementations of its methods, you can implement a typeclass by providing implementations of its operations.<\/p>\n In Scala, you implement the operations of a typeclasses using a language construct called an implicit parameter. The implicit parameter attaches the typeclass operations to a meta-object that can be passed around the program invisibly, providing the typeclass’s operations.<\/p>\n Let’s take a look at an example. An operation that comes up very frequently in any kind of data processing code is reduction: taking a collection of values of some type, and combining them into a single value. Taking the sum of a list of integers, the product of an array of floats, and the concatenation of a list of strings are all examples of reduction. Under the covers, these are all similar: they’re taking an ordered group of values, and performing an operation on them. Let’s look at a couple of examples of this:<\/p>\n When you look at the code, they look very similar. They’re both just instantiations of the same structural pattern:<\/p>\n The types are different; the actual operation used to combine the values is different; the base value in the code is different. But they’re both built on the same pattern:<\/p>\n We can capture that concept by writing an interface (a trait, in Scala terms) that captures it; that interface is called a typeclass. It happens that this concept of reducible values is called a monoid in abstract algebra, so that’s the name we’ll use.<\/p>\n We can read that as saying “A is a monoid if there are implementations of empty and combine that meet these constraints”. Given the declaration of the typeclass, we can implement it as an object which provides those operations for a particular type:<\/p>\n Using our implementation of We can use that to reduce a list of floats:<\/p>\n And we can do a bit better than that! We can set up an implicit<\/em>, so that we don’t need to pass the monoid implementation around. In Scala, an implicit is a kind of dynamically scoped value. For a given type, there can be one implicit value of that type in effect at any point in the code. If a function takes an implicit parameter of that type, then the nearest definition in the execution stack will automatically be inserted if the parameter isn’t passed explicitly.<\/p>\n And as long as there’s a definition of the Now, anywhere that the Using this idea of a monoid, we’ve captured the concept of reduction in a common abstraction. Our notion of reduction doesn’t care about whether we’re reducing strings by concatenation, integers by addition, floats by multiplication, sets by union. Those are all valid uses of the concept of a monoid, and they’re all easy to implement using the monoid typeclass. The concept of monoid isn’t a difficult one, but at the same time, it’s not necessarily something that most of us would have thought about as an abstraction.<\/p>\n We’ve got a typeclass for a monoid; now, we’ll try to connect it into category theory. It’s a bit tricky, so we won’t cover it all at once. We’ll look at it a little bit now, and we’ll come back to it in a later lesson, after we’ve absorbed a bit more.<\/p>\n For most of us, if we’ve heard of monoids, we’ve heard of them in terms of set theory and abstract algebra. So in that domain, what’s a monoid?<\/p>\n A monoid is a triple That\u2019s all just a formal way of saying that a monoid is a set with a binary associative operator and an identity value. The set of integers can form a monoid with addition as the operator, and 0 as identity. Real numbers can be a monoid with multiplication and 1. Strings can be a monoid with concatenation as the operator, and empty string as identity.<\/p>\n But we can look at it in a different way, too, by thinking entirely in terms of function. How can we tell that 2 is a function which adds two to things?<\/p>\n If we compose it with 3 (the function that adds three to things), we get 5 (the function that adds five to things). And how do we know that? Because it’s the same thing that we get if we compose 3 with 1, and then compose the result of that with 1 again. 3+1+1=5, and 3+2=5. We can also tell that it’s 2, because if we just take 1, and compose it with itself, what we’ll get back is the object that we call 2.<\/p>\n In this scheme, all of the numbers are related not by arithmetic, not by an underlying concept of quantity or cardinality or ordinality, but only by how they compose with each other. We can’t see anything else – all we have are these functions. But we can recognize that they are the natural numbers that we’re familiar with.<\/p>\n Looking at it this way, we can think of the world of natural numbers as a single point, which represents the set of all natural numbers. And around that point, we’ve got lots and lots of arrows, each of which goes from that point back to itself. Each of those arrows represents one number. The way we tell them apart is by understanding which arrow we get back when we compose them. Take any arrow from that point back to that point, and compose it with the arrow 0, and what do you get? The arrow you started with. Take any arrow that you want, and compose it with 2. What do you get? You get the same thing that you’d get if you composed it with 1, and then composed it with one again.<\/p>\n That dot, with those arrows, is a category.<\/p>\n What kind of advantage do we get in going from the algebraic notion of a set with a binary operation, to the categorical notion of an object with a bunch of composable arrows? It allows to understand a monoid purely as a structure, without having the think about what the objects are, or what the operator means.<\/p>\n Now, let’s jump back to our monoid typeclass for a moment.<\/p>\n We can understand this as being a programmable interface for the categorical object that we just described. All we need to do is read “:” as “is an arrow in”: It says that A is a monoid if:<\/p>\n There are, of course, other conditions – combine needs to be associative, and empty needs to behave as the identity value. But just like when we write an interface for, say, a binary search tree, the interface only defines the structure not the ordering condition, the typeclass defines the functional structure of the categorical object, not the logical conditions.<\/p>\n This is what categories are really all about: tearing things down to a simple core, where everything is expressed in terms of arrows. It\u2019s almost reasoning in functions, except that it\u2019s even more abstract than that: the arrows don\u2019t need to be functions – they just need to be composable mappings from things to things.<\/p>\n We can abstract a bit more, and look at the entire construction, including the identity and associativity constraints entirely in terms of arrows. To really understand this, we\u2019ll need to spend some time diving deeper into the actual theory of categories, but as a preview, we can describe a monoid with the following pair of diagrams (copied from wikipedia):<\/p>\nStart with an Example: Monoids<\/h1>\n
Monoids in Code<\/h2>\n
def reduceFloats(floats: List[Float]): Float =\n floats.foldRight(0)((x, y) => x + y)\n\ndef reduceStrings(strings: Seq[String]): String =\n strings.foldRight(\"\")((x, y) => x.concat(y))\n<\/pre>\n
def reduceX(xes: List[X]): X =\n xes.foldRight(xIdentity)((a, b) => Xcombiner(a, b))\n<\/pre>\n
\n
Float<\/code> or String<\/code>. Everything we care about in reduction is a connected with this type.<\/li>\nList[Float]<\/code>, and in the other, it’s a Seq[String]<\/code>. The type doesn’t matter, as long as we can iterate over it.<\/li>\n0<\/code> for the floats, and \"\"<\/code> (the empty string) for the strings.<\/li>\n+<\/code> for the floats, and concat<\/code> for the strings.<\/li>\n<\/ul>\ntrait Monoid[A] {\n def empty: A\n def combine(x: A, y: A): A\n}\n<\/pre>\nobject FloatAdditionMonoid extends Monoid[Float] {\n def empty: Float = 0.0\n def combine(x: Float, y: Float): Float = x + y\n}\n\nobject StringConcatMonoid extends Monoid[String] {\n def empty: String = \"\"\n def combine(x: String, y: String): String = x.concat(y)\n}\n<\/pre>\nFloatAdditionMonoid<\/code> implements the typeclass Monoid<\/code> for the type Float<\/code>. And since we can write an implementation of Monoid<\/code> for Float<\/code> or String<\/code>, we can say that the types Float<\/code> and String<\/code> are instances of the typeclass Monoid<\/code>.<\/p>\nMonoid<\/code>, we can write a single, generic reduction operator now:<\/p>\ndef reduce[A](values: Seq[A], monoid: Monoid[A]): A =\n values.foldRight(monoid.empty)(monoid.combine)\n<\/pre>\n
reduce([1.0, 3.14, 2.718, 1.414, 1.732], FloatAdditionMonoid)\n<\/pre>\n
def reduce[A](values: Seq[A])(implicit A: Monoid[A]): A =\n list.foldRight(A.empty)(A.combine)\n<\/pre>\n
Monoid<\/code> for a type A<\/code> in scope, we can can use that now by just writing:<\/p>\nimplicit object FloatAdditionMonoid extends Monoid[Float] {\n def empty: Float = 0.0\n def combine(x: Float, y: Float): Float = x + y\n}\n\nval floats: List[Float] = ...\nval result = reduce(floats)\n<\/pre>\nFloatAdditionMonoid<\/code> declaration is imported, you can call reduce on any sequence of floats, and the implicit value will automatically be inserted.<\/p>\nFrom Sets to Arrows<\/h3>\n
\n
\n
\nLet’s forget about the numbers as individual values, and instead, let’s think about them in functional terms. Every number is a function which adds itself to its parameter. So “2” isn’t a number, it’s a function which adds two to anything.<\/p>\ntrait Monoid[A] {\n def empty: A\n def combine(x: A, y: A): A\n}\n<\/pre>\n\n
Deeper Into Arrows<\/h2>\n
![\"\"](\"https:\/\/i0.wp.com\/www.goodmath.org\/blog\/wp-content\/uploads\/2018\/10\/cat-monoid.jpg\")
<\/a><\/p>\n