This post is part of a series on Category Theory for Scala I am writing based on Bartosz Milewski Book on the same topic. As I read the book, I take notes, I try to solve the Challenges Bartosz proposes in Scala and make them public in this posts. You can find all the code in my github repo elbaulp/Scala-Category-Theory, you can also visit the Table Of Contents of this series.

# CHANGELOG

*Thanks to Jesús López for pointing out some errors*

# Introduction

This is the first post I'm going to write about **Category Theory**.

I've been wanting to learn Category Theory for a while, since it seems to have practical applications in software.

This series will be based on the great book **Bartosz Milewski** wrote some time ago. To contribute to this cause, I've implemented the exercises he proposed in scala, and also wrote *Property Tests* with `scalacheck`

. I hope you enjoy this series, and don't hesitate to comment or fixing/improving this content.

**Help me keep writing**

- “Whitelist” me in your
**ad blocker** - Why I removed
**Google Analytics** - Use my
**Amazon**link - Download a
**free EBook** - Other ways to
**support me**

# Category: The Essence of Composition

What is a *category*?, from Wikipedia:

In mathematics, a category is an algebraic structure similar to a group but without requiring inverse or closure properties. It comprises "objects" that are linked by "arrows". A category has two

basic properties:the ability to compose the arrowsassociativelyand the existence of anidentity arrowfor each object. A simple example is the category of sets, whose objects are sets and whose arrows are functions.

In short, a *category* is form by **objects and arrows**, and they can compose. This is best shown with an image:

Each arrow can be **composed**, f.e: If `A -> B`

and `B -> D`

then there must be an arrow from `A -> D`

. Arrows can be called **morphisms**, they can be composed. In the image above, you have:

`f: A -> B`

`g: B -> D`

- If you compose those two: you'll also have
`h: A -> D`

.

Composition reads from *right to left:* `g∘f`

would be `g(f(x))`

.

# Properties of Composition

**Associativity:**`f∘(g∘h) == (f∘g)∘h == f∘g∘h`

.- For every object exists an
**Identity Arrow**, it goes from the object to itself:`f∘IDₐ = f == IDₐ∘f = f`

, as shown below:

# Examples in Scala

Now that I've shown you a bit of theory, lets implement it in **scala**. As I said at the beginning of the post, I will be using *property based tests* to check the implementation is correct and satisfy the *category properties*, that is, **Identity** and **associativity**.

Here is the definition of a simple *Category* (Its actually an instance of a Category, the category **Hask** in this case). A **Hask** category has **types as objects** and **arrows as functions**. You can check the full code at Category.scala in my github repo.

```
object Category {
def Id[T](x: T) = x
def compose[A, B, C](f: A => B, g: B => C): A => C =
f andThen g
}
```

Simple enough, an *identity* function and a function that compose two functions. Now lets try to prove this implementation is correct using *property based* tests.

# Property tests

## Identity Property

To simplify the post, I'm going to show only the important snippets of code, you can check the entire code at github.

```
property("a == Id(a)") {
check(forAll { i:String =>
Category.Id(i) === i
})
}
property("Id∘f = f") {
check(forAll { i: Int =>
Category.Id(square(i)) === square(i)
})
}
property("f∘Id = f") {
check(forAll { i: Int =>
f(Category.Id(i)) === f(i)
})
}
```

The first property states that for all `Strings`

you can possibly pass to the `identity`

function, the `identity`

will always be the `String`

the function was passed to as argument.

The second and third properties states that it does not matter how you compose the `identity`

function with another function `f`

, it will always be that function `f`

.

## Associativity Property

```
property("Associativity: h∘(g∘f) = (h∘g)∘f = h∘g∘f"){
check(forAll { i: Int =>
Category.compose(Category.compose(f, g), h)(i) === Category.compose(f, Category.compose(g, h))(i)
})
}
```

As you can see, this test states that the associative property holds.

If you execute this property tests, all pass:

That's it for this first part, I hope you enjoy it, I would like to hear your opinion, *comment below!*

# Resources

Spot a typo?: Help me fix it by contacting me or commenting below!