Connecting...

# Arrow 101 — Modelling a real world problem with Semigroups by Leandro Borges Ferreira

Are you looking to expand your knowledge on Category Theory? This article written by Leandro Borges Ferreira presents how to use a tool from Category Theory to model a simple, yet real scenario. Happy learning!

'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.

Like this:

Card1

— Charge 1, Charge 2; Limit \$400

Card2

— Charge 3, Charge 4; Limit \$800

After deleting Card1, we just have Card2:

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:

``````1 data class VirtualCard(
2         val id: Long,
3         val chargeList: List<Charge>,
4         val cvc: String,
5         val expireDate: LocalDate
6 ) {
7     companion object {
8         fun semigroup() = object : VirtualCardSemigroup {}
9    }
10 }``````

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:

``````1 @instance(VirtualCard::class)
2 interface VirtualCardSemigroup : Semigroup<VirtualCard> {
3
4     override fun VirtualCard.combine(b: VirtualCard): VirtualCard =
5            VirtualCard(
6                    this.id,
7                    this@combine.chargeList + b.chargeList,
8                    this.cvc,
9                    this.expireDate
10            )
11 }``````

We keep the data of the first card and combine the charges of the two. Easy, right?

The same goes for Bills:

``````1 data class Bill(val amount: Double, val dueDate: LocalDate) {
2     companion object {
3        fun semigroup() = object : BillSemigroup {}
4     }
5 }
6
7 @instance(Bill::class)
8 interface BillSemigroup : Semigroup<Bill> {
9
10     override fun Bill.combine(b: Bill): Bill = Bill(
11             this.amount + b.amount,
12             dueDate
13     )
14 }
``````

So now we have our Semigroups. If we need to sum then, we can use the combineAll method. Like this:

``1 val totalBill = Bill.semigroup().combineAll(bill1, bill2, bill3)``

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:

``1 testImplementation "io.arrow-kt:arrow-test:0.7.2"``

And then you can test your Semigroups. Here is an example:

``````1 class BillSemigroupTest {
2
3     @Test
4     fun `test to assert that Bill is a Monoid`() {
5         val bill1 = Bill(100.0, LocalDate.now())
6         val bill2 = Bill(200.0, LocalDate.now().plusDays(2))
7         val bill3 = Bill(300.0, LocalDate.now().plusDays(3))
8
9         val equality : Eq<Bill> = Eq.invoke { b1, b2 ->
10             b1.shouldEqual(b2)
11             true
12         }
13
14         SemigroupLaws.laws(Bill.semigroup(), bill1, bill2, bill3, equality).forEach {
15             it.test()
16         }
17     }
18 }``````

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)

//Also

This is the same relation as:

(1 + 2) + 3 = 1 + (2 + 3) = 6

//or

("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:

``1 data class Charge(val id: Long, val amount: Double, val dateTime: LocalDate)``

A very simple class. To work with our Entities we need a class to represent our database. A simple interface could be:

``````1 nterface EntityDAO<T> {
2
3     fun getData() : List<T>
4
5     fun getEntity(id: Long) : Option<T>
6
7     fun removeEntity(id: Long) : Option<T>
8
9     fun saveEntity(entity: T) : Option<T>
10 }``````

And a simple implementation could be:

``````1 class VirtualCardDb : EntityDAO<VirtualCard> {
2
3     private val cardsMap: MutableMap<Long, VirtualCard> =
4             mutableMapOf(
5                     Pair(1L, VirtualCard(1,
6                             listOf(Charge(1, 100.0, LocalDate.of(2018, 3, 3))),
7                             "123",
8                             LocalDate.of(2020, 1, 1))),
9                     // Put more VirtualCards here
10             )
11
12     override fun getData(): List<VirtualCard> =
13         cardsMap.values.toList()
14
15     override fun removeEntity(id: Long) : Option<VirtualCard> =
16         cardsMap.remove(id).toOption()
17
18     override fun getEntity(id: Long): Option<VirtualCard> =
19         cardsMap[id].toOption()
20
21     override fun saveEntity(entity: VirtualCard) : Option<VirtualCard> =
22         cardsMap.put(entity.id, entity).toOption()
23
24 }``````

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:

``````1 fun mergeCards(newCardId: Long, oldCardId: Long) =
2     VirtualCardDb() pipe { dao ->
4             val (newCard, oldCard) = Option.applicative()
5                     .tupled(dao.getEntity(newCardId), dao.getEntity(oldCardId))
6                     .fix()
7                     .bind()
8
9             dao.saveEntity(VirtualCard.semigroup().run { newCard + oldCard }).bind()
10             dao.removeEntity(oldCard.id).bind()
11         }
12 }``````

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:

``````1 private fun totalBill(dueDate: LocalDate, virtualCards: Iterable<VirtualCard>) : Bill =
2         virtualCards
3             .map { virtualCard -> virtualCardToBill(virtualCard, dueDate) }
4             .reduce { acc, bill -> Bill.semigroup().run { acc + bill } }
5
6 fun virtualCardToBill(virtualCard: VirtualCard, dueDate: LocalDate) : Bill =
7         Bill(totalAmountFromCharges(virtualCard.chargeList), dueDate)
8
9 private fun totalAmountFromCharges(chargeList: Iterable<Charge>) : Double =
10         chargeList.sumByDouble { charge -> charge.amount }``````

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:

``1 fun getTotalBill(localDate: LocalDate) = totalBill(localDate, VirtualCardDb().getData())``

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:

``````1 fun <A> mergeEntity(newId: Long, oldId: Long, dao: EntityDAO<A>, semigroup: Semigroup<A>) =
3         Option.applicative().tupled(dao.getEntity(newId), dao.getEntity(oldId))
4                 .fix()
5                 .map { (newEntity, oldEntity) ->
6                     dao.saveEntity(semigroup.run { newEntity + oldEntity })
7                 }.bind()
8
9         dao.removeEntity(oldId).bind()
10     }``````

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:

``````1 interface DeferredEntityDAO<T> {
2
4
6
8
10
11 }``````

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:

``````1 class DeferredDAO<T>(private val dao: EntityDAO<T>) : DeferredEntityDAO<T> {
2
4             Kind<F, List<T>> = monadDefer { dao.getData() }
5
7             Kind<F, Option<T>> = monadDefer { dao.getEntity(id) }
8
10             Kind<F, Option<T>> = monadDefer { dao.removeEntity(id) }
11
13             Kind<F, Option<T>> = monadDefer { dao.saveEntity(entity) }
14
15 }``````

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:

``````1 fun <F, A> mergeDeferred(newId: Long,
2                          oldId: Long,
3                          dao: DeferredEntityDAO<A>,
5                          semigroup: Semigroup<A>): Kind<F, Option<A>> =
7             val newEntity = dao.getEntity(monad, newId).bind()
8             val oldEntity = dao.getEntity(monad, oldId).bind()
9
11                     Option.applicative()
12                     .tupled(newEntity, oldEntity)
13                     .fix()
14                     .map { (newEntity, oldEntity) -> semigroup.run { newEntity + oldEntity } }
15                     .toEither {
16                         Exception("Ops!")
17                     })
18                     .bind()
19
22         }``````

Ok… The code looks different. Let's go step by step. First, we have:

``````1 fun <F, A> mergeDeferred(newId: Long,
2                          oldId: Long,
3                          dao: DeferredEntityDAO<A>,
5                          semigroup: Semigroup<A>): Kind<F, Option<A>> =``````

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:

``````1 monad.bindingCatch {
2             val newEntity = dao.getEntity(monad, newId).bind()
3             val oldEntity = dao.getEntity(monad, oldId).bind()
4             [...]``````

Lastly, we combine our entities, save the combination and than delete the old card.

``````1 val newEntity = dao.getEntity(monad, newId).bind()
2 val oldEntity = dao.getEntity(monad, oldId).bind()
3
5     Option.applicative()
6     .tupled(newEntity, oldEntity)
7     .fix()
8     .map { (newEntity, oldEntity) -> semigroup.run { newEntity + oldEntity } }
9     .toEither {
10         Exception("Ops!")
11     })
12     .bind()
13

But our computation was never run, because everything is being deferred. We need to invoke the function. It not hard:

``````1 fun concreteMerge() {
2     mergeDeferred(1, 2, DeferredDAO(VirtualCardDb()), IO.monadDefer(), VirtualCard.semigroup())
3             .fix()
4             .attempt()
5             .unsafeRunSync()
6             .fold({
7                 //It didn't succeed
8             }, {
9                 //Success!
10             })
11 }``````

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:

``````1 fun mergeCards(newCardId: Long, oldCardId: Long) =
2     VirtualCardDb() pipe { dao ->
4             val (newCard, oldCard) = Option.applicative()
5                     .tupled(dao.getEntity(newCardId), dao.getEntity(oldCardId))
6                     .fix()
7                     .bind()
8
9             dao.saveEntity(VirtualCard.semigroup().run { newCard + oldCard }).bind()
10             dao.removeEntity(oldCard.id).bind()
11         }
12 }
14
15 fun getTotalBill(localDate: LocalDate) = totalBill(localDate, VirtualCardDb().getData())
16
17 private fun totalBill(dueDate: LocalDate, virtualCards: Iterable<VirtualCard>) : Bill =
18         virtualCards
19             .map { virtualCard ->
20                 virtualCardToBill(virtualCard, dueDate)
21             }
22             .reduce { acc, bill -> Bill.semigroup().run { acc + bill } }
23
24 fun virtualCardToBill(virtualCard: VirtualCard, dueDate: LocalDate) : Bill =
25         Bill(totalAmountFromCharges(virtualCard.chargeList), dueDate)
26
27 private fun totalAmountFromCharges(chargeList: Iterable<Charge>) : Double =
28         chargeList.sumByDouble { charge -> charge.amount }
29
30 fun <A> mergeEntity(newId: Long, oldId: Long, dao: EntityDAO<A>, semigroup: Semigroup<A>) =
32         Option.applicative().tupled(dao.getEntity(newId), dao.getEntity(oldId))
33                 .fix()
34                 .map { (newEntity, oldEntity) ->
35                     dao.saveEntity(semigroup.run { newEntity + oldEntity })
36                 }.bind()
37
38         dao.removeEntity(oldId).bind()
39     }
40
41 fun <F, A> mergeDeferred(newId: Long,
42                          oldId: Long,
43                          dao: DeferredEntityDAO<A>,
45                          semigroup: Semigroup<A>): Kind<F, Option<A>> =
47             val newEntity = dao.getEntity(monad, newId).bind()
48             val oldEntity = dao.getEntity(monad, oldId).bind()
49
51                     Option.applicative()
52                     .tupled(newEntity, oldEntity)
53                     .fix()
54                     .map { (newEntity, oldEntity) -> semigroup.run { newEntity + oldEntity } }
55                     .toEither {
56                         Exception("Ops!")
57                     })
58                     .bind()
59
62         }
63
64 fun concreteMerge() {
65     mergeDeferred(1, 2, DeferredDAO(VirtualCardDb()), IO.monadDefer(), VirtualCard.semigroup())
66             .fix()
67             .attempt()
68             .unsafeRunSync()
69             .fold({
70                 //It didn't succeed
71             }, {
72                 //Success!
73             })
74 }``````

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!'

This article was written by Leandro Borges Ferreira and originally posted on Medium.com