Arrow 101 — Modelling a real world problem with Semigroups
1 — Intro
FP offers us many tools to create more terse and less imperative code. But besides knowing how to use then, it is also important to learn to see our problems in a mathematical way.
In the article I will present how to use a tool from Category Theory to model a simple, yet real scenario: Semigroups. You don't need to be a super theoretical programer or be a master of calculus. This concept is easy, it just have some weird name.
I hope you enjoy it and give it a try!
If you would like to access a github repository with all the code, look here: https://github.com/leandroBorgesFerreira/ArrowModel
2 — The Problem
Let's suppose we work for a fintech called PurpleBank. It has many financial services and it is growing their number. At some point, the company decides to offer virtual credit cards for the costumers, so they can buy online in a more secure way.
A virtual card can be deleted, but you cannot simply make the charges in that card disappear. You need to transfer all the charges to another card right before deleting it. The credit limit for the old card should also go to the other card, since each card was its own limit. So the old card will be combined to another one.
— Charge 1, Charge 2; Limit $400
— Charge 3, Charge 4; Limit $800
After deleting Card1, we just have Card2:
— Charge 1, Charge 2, Charge 3, Charge 4; Limit $1200
The user should also be able to pay for each card bill individually or pay for all of then at once. So virtual card can be transformed into Bills. Bills also can be combined.
So, there's a tool that can help us to solve this problem, Semigroups.
2.1 — Virtual Cards and Bills as Semigroups
I'm not going to give you an explanation about what is a Semigroup. You can find some resources about it over the internet. Category Theory for Programmers and this article are some good sources, take a look and you will get it =]
So, a Semigroup should be combinable, right? Like numbers, you can combine then by adding: 3 + 2 = 5. String are easy to see it too: "Cheers from " + "Brazil" = "Cheers from Brazil". But… uhm… Virtual Card are not so obvious, right? Let's take a look of what would be a data class for a VirtualCard:
The only obvious part to sum here is the chargeList, all we have to do is to concatenate to another list.
But the chargeList is the only part that we actually would like to keep. We will sum one card to another one, so we need to keep the data of one of the two cards and keep all the charges from both, the rest will be deleted.
So we have this Semigroup for VirtualCard:
We keep the data of the first card and combine the charges of the two. Easy, right?
The same goes for Bills:
So now we have our Semigroups. If we need to sum then, we can use the combineAll method. Like this:
But you might be thinking: “Wait, so we have this:”
virtualCard1 + virtualCard2 ≠ virtualCard2 + virtualCard1
“Is it right? If we invert the order of the sum, we change the result, that’s weird”
Actually, it is right.
We don’t need the commutative property. As long we have associative property, it is a Semigroup. So we are good to go. Just remember that the order matters in this sum and that’s probably what you’ll see in real case scenarios. It our example the virtualCard2 must be the one that is going to be deleted.
Arrow provides a library to tests if you correctly implemented your code respecting the concept of Category Theory that you can using (In this example, Semigroup).
You can include the library of Arrow tests like this:
And then you can test your Semigroups. Here is an example:
SemigroupLaws are going to verify that the Semigroup create by you follow the rules of a Semigroup, so you can securely use it in your program. This Laws is going if you are respecting the associative property:
(SemiG1 + SemiG2) + SemiG3 = SemiG1 + (SemiG2 + SemiG3)
This is the same relation as:
(1 + 2) + 3 = 1 + (2 + 3) = 6
("Cheer's " + "from ") + "Brazil" =
"Cheer's " + ("from " + "Brazil")
= "Cheer's from Brazil"
3— Modelling our "database"
Now we know enough to solve our problem. Before going further, let me show how I am modeling our Charge:
A very simple class. To work with our Entities we need a class to represent our database. A simple interface could be:
And a simple implementation could be:
So that's our database DAO. That's not our focus for now, so let's move along.
4 — Solving the problem
4.1 — Virtual Cards
Before deleting our old card, we need to fuse it with an existing card. We also need to guarantee that our computation only runs if both IDs passed to us are valid. So we have this logic to merge two cards and end up with only one:
We use Monad Comprehensions, Applicative Builder and a map.
Monad Comprehensions is feature available in many languages. It makes possible to write sequential actions in a way what feels natural and easy to read. You can check about it here.
The Applicative Builder receives all our Options and create a new one in a Tuple with all the values passed to it. This way, the will only run the map method if both options have a value. If any of the two have None as value, the resulting Option will have None as result and our map will be circuit breaked.
After this, we combine the cards in our map, save the combined card and then delete the old one.
This way, we are able to deal with our virtual cards as a Semigroup, we can combine than to create a delete logic. This code will get more interesting latter when we improve this code. For now, let's take a look in our Bills.
4.2 — Bills
Our card got deleted and combined with another card. So, time to pay the Bill.
To create a total Bill, all we have to do is to map our VirtualCard to the Bill that it represents. Take a look at the code:
We morph our VirtualCards to Bills, then, as Bill are also Semigroups, we combine then into a single Bill. We can call this method like this:
And that's it. With Semigroups we can model many problems to morphisms and combinations of our data. Bills, for example, could have the same behaviour of VirtualCards. Maybe you have Bills that you would like to pay every month, but you would to pay then all at once (or some of then at once) and gain a discount. So the idea of merging information can be used for more than just virtual cards. Perhaps we can extend our code:
Now we have a small DSL. This piece of code could be used to Virtual Cards, Bills and any other Entity that has the same logic of combine before delete. This way we can create building blocks that are going to be used in our whole system and Arrow can help us to create a nice abstract and concise code.
The code doesn't look bad by now, but there's a little problem with our DSL: Our functions are not pure. The function mergeEntity is causing a side effect and this should be avoided. Our computation could be deferred and the write in our database could happen only in a layer that side effects are acceptable. So let's keep working.
5 — Improving the code
Let's create an interface for our DAO with deferred computation. First, we need a Monad capable of deferring our computation (You can look here for a tutorial about Monads). Second, we need to define a return type that changes accordingly to the Monad chosen. Like this:
MonadDefer can be any kind Monad capable of defering our computation, it can be IO or an ObservableK (from RxJava integration) and Kind is a Higher Kinded Type (take a look here for a tutorial), it is translated to F<List<T>> or F<Option<T>>. This code will be concretised as the type of our MonadDefer latter on.
So basically our functions are saying: "Give me a certain class capable to postpone some behaviour and I will return you some data based on what you offered me". It seams fair.
So we can have an actual class for our interface:
All this class does is to apply the MonadDefer on the EntityDAO. That's it, the same behaviour, but inside a different container. To use this new DAO, we need to change our mergeEntity functionThis. So now we have this:
Ok… The code looks different. Let's go step by step. First, we have:
Now we receive our DeferredEntityDAO and a MonadDefer. By passing in a MonadDefer we will be able to concretise our implementation, this is why it is needed. Then we use monad comprehensions to bind our values and make our code look like imperative code:
Lastly, we combine our entities, save the combination and than delete the old card.
But our computation was never run, because everything is being deferred. We need to invoke the function. It not hard:
And that's it, we did our solution in a pure and abstract way. Our code doesn't depend of an specific Monad, you can use any that you would like to. That means that you can change from technologies (like between Coroutines and RxJava) easily.
The code is easier to maintain because you can add new technologies/classes as long as they keep being Monads. It is also easier to reason about because you can cause all side effects at one single place.
I am pasting all the code here so you can take a look at the big picture:
This final version of the code may look a lot generic at first (the idea of using Kind<F, T> totally blowed my mind at first hahaha), but if you give it a try, you can definitely understand the idea and implement using this pattern without problems.
I hope you enjoyed the article and you start using Arrow and Category Theory. Happy coding!
If you enjoyed this article, please click on the clap button =]