Author

Alejandro Alcalde

Data Scientist and Computer Scientist. Creator of this blog.

Alejandro Alcalde's posts | Porfolio

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.

<!–ad–>

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 arrows associatively and the existence of an identity arrow for 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

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

Identity Property

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

Category: The Essence of Composition

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

Categories:

dev

Tags:

Maybe this posts are also worth reading

«« Cryptography 101: Mathematical basis (I) - Modular arithmetic Biometrics applied to security - Pattern Recognition »»