Geekly Articles each Day
📜 ⬆️ ⬇️

Money monoid


Mark Seeman talks about functional programming quickly and easily. To do this, he began writing a series of articles on the relationship between design patterns and category theory . Any OOshnik, which has 15 minutes of free time, will be able to get into their own hands a fundamentally new set of ideas and insights related not only to the functional area, but also to the correct object-oriented design. The crucial factor is that all the examples are real C #, F #, and Haskell code .

This habrapos is the second article in a series of articles about monoids:


Before we begin, I would like to make a small digression regarding the title of the article. In 2003, Kent Beck’s book, Extreme Programming: Development Through Testing , which in the original is called Test-Driven Development by example, came out, which had already become a bestseller. One of such “example” was “Money example” - an example of writing and refactoring an application that can perform multi-currency operations, for example, adding 10 dollars and 10 francs. The title of this article is a reference to this book, and I strongly recommend that you familiarize yourself with the first part in order to better understand what the article is about.

"Money example" Kent Beck has some interesting properties.

In short, a monoid is an associative binary operation that has a neutral element (sometimes also called a unit ).
')
In the first part of his book, Kent Beck explores the possibility of creating a simple and flexible "monetary API" using the principle of "development through testing." As a result, he gets a solution, the design of which requires further study.

Kent Beck API


This article uses the code from Kent Beck’s book, translated by Yavar Amin into C # (the original code was written in Java), which I forked and added .

Kent Beck, in his book, was engaged in the development of an object-oriented API capable of processing money in several currencies, with the ability to work with expressions, such as "5 USD + 10 CHF". By the end of the first part, it creates an interface that (translated into C #) looks like this:

public interface IExpression { Money Reduce(Bank bank, string to); IExpression Plus(IExpression addend); IExpression Times(int multiplier); }

The Reduce method converts an IExpression object to a certain currency (to parameter), represented as a Money object. This is useful if you have an expression that has multiple currencies.

The Plus method adds an IExpression object to the current IExpression object and returns a new IExpression . It can be money in one currency or in several.

The Times method multiplies IExpression by a specific multiplier. You probably noticed that in all the examples we use integers for the multiplier and the sum. I think Kent Beck did this in order not to complicate the code, but in real life we ​​would use fractional numbers when working with money (for example, decimal ).

The metaphor of "expression" is that we can simulate working with money, like working with mathematical expressions. A simple expression will look like 5 USD , but there can also be 5 USD + 10 CHF or 5 USD + 10 CHF + 10 USD . Although you can easily calculate ( reduce ) some simple expressions, for example, 5 CHF + 7 CHF , you cannot calculate the expression 5 USD + 10 CHF if you do not have the exchange rate. Instead of trying to immediately calculate monetary transactions, in this project we create a tree of expressions, and only then perform its transformation. Sounds familiar, doesn't it?

Kent Beck in his examples implements the IExpression interface IExpression two classes:


If we want to describe the expression 5 USD + 10 CHF , it will look something like this:

 IExpression sum = new Sum(Money.Dollar(5), Money.Franc(10));

where Money.Dollar and Money.Franc are two static factory methods that return Money objects.

Associativity


Have you noticed that Plus is a binary operation? Can we consider it a monoid?

To be a monoid, it must satisfy the laws of the monoid , the first of which says that the operation must be associative. This means that for three IExpression objects, x , y and z , the expression x.Plus(y).Plus(z) must be equal to x.Plus(y.Plus(z)) . How should we understand equality here? The return value of the Plus method is the IExpression interface, and the interfaces have no such thing as equality. So, either, equality depends on specific implementations ( Money and Sum ), where we can define appropriate methods, or we can use test matching (test pattern, test-specific equality , - approx. Lane ).

The library for testing xUnit.net supports test compliance through the implementation of custom comparators (for a detailed study of the possibilities of unit testing, the author proposes to take his Advanced Unit Testing course at Pluralsight.com). However, in the original Money API it is already possible to compare objects of type IExpression !

The Reduce method can convert any IExpression to an object of type Money (that is, to a single currency), and since Money is an object-value, it has structural equality (for more information about value objects and their features, you can read, for example, here ). And we can use this property to compare IExpression objects. All we need is the exchange rate.

In his book, Kent Beck uses a 2: 1 exchange rate between CHF and USD. At the time of this writing, the exchange rate was CHF 0.96 to the dollar, but since the example code everywhere uses whole numbers for money transactions, I will have to round the rate to 1: 1. This, however, is a rather foolish example, so instead I will stick to the original 2: 1 exchange rate.

Now let's write the adapter between Reduce and xUnit.net as the IEqualityComparer<IExpression> class:

 public class ExpressionEqualityComparer : IEqualityComparer<IExpression> { private readonly Bank bank; public ExpressionEqualityComparer() { bank = new Bank(); bank.AddRate("CHF", "USD", 2); } public bool Equals(IExpression x, IExpression y) { var xm = bank.Reduce(x, "USD"); var ym = bank.Reduce(y, "USD"); return object.Equals(xm, ym); } public int GetHashCode(IExpression obj) { return bank.Reduce(obj, "USD").GetHashCode(); } }

You have noticed that the comparator uses a Bank object with a 2: 1 exchange rate. The Bank class is another object from the Kent Beck code. It itself does not implement any interface, but is used as an argument to the Reduce method.

To make our test code more readable, add an auxiliary static class:

 public static class Compare { public static ExpressionEqualityComparer UsingBank = new ExpressionEqualityComparer(); }

This will allow us to write an assertion that checks equality for the associativity operation:

 Assert.Equal( x.Plus(y).Plus(z), x.Plus(y.Plus(z)), Compare.UsingBank);

In my fork of the Yavar Amin code, I added this assertion to the FsCheck test, and it is used for all Sum and Money objects that FsCheck generates.

In the current implementation, IExpression.Plus associative, but it's worth noting that this behavior is not guaranteed, and here's why: IExpression is an interface, so someone can easily add a third implementation that will break the associativity. Conventionally, we will assume that the operation Plus associative, but the situation is delicate.

Neutral element


If we agree that IExpression.Plus associative, then this is a candidate for monoids. If there exists a neutral element, then this is definitely a monoid.

Kent Beck did not add a neutral element to his examples, so add it yourself:

 public static class Plus { public readonly static IExpression Identity = new PlusIdentity(); private class PlusIdentity : IExpression { public IExpression Plus(IExpression addend) { return addend; } public Money Reduce(Bank bank, string to) { return new Money(0, to); } public IExpression Times(int multiplier) { return this; } } }

Since there can be only one neutral element, it makes sense to make it a singleton . The private class PlusIdentity is a new implementation of IExpression that does nothing.

The Plus method simply returns the input value. This is the same behavior as for adding numbers. When added, zero is a neutral element, and the same thing happens here. This is more clearly seen in the Reduce method, where the calculation of a “neutral” currency is simply reduced to zero in the requested currency. Finally, if you multiply a neutral element by something, you get a neutral element. Here, interestingly, PlusIdentity behaves like a neutral element for a multiplication operation (1).

Now we write tests for any IExpression x :

 Assert.Equal(x, x.Plus(Plus.Identity), Compare.UsingBank); Assert.Equal(x, Plus.Identity.Plus(x), Compare.UsingBank);

This is a property test, and it is executed for all x generated by FsCheck. Caution applied to associativity is also applicable here: IExpression is an interface, so you cannot be sure that Plus.Identity will be a neutral element for all implementations of IExpression that anyone can create, but for three existing implementations, monoid laws are preserved.

Now we can assert that the operation IExpression.Plus is a monoid.

Multiplication


In arithmetic, the multiplication operator is called “time”. When you write 3 * 5 , it literally means that you have 3 five times (or 5 three times?). In other words:
3 * 5 = 3 + 3 + 3 + 3 + 3
Is there a similar operation for IExpression ?

Perhaps we can find a clue in the Haskell language, where monoids and semigroups are part of the main library. Later you will learn about semigroups, but for the moment just note that the Semigroup class defines the stimes function, which is of type Integral b => b -> a -> a . This means that for any integer type (16-bit integer, 32-bit integer, etc.), the stimes function takes an integer and a value a and “multiplies” the value by a number. Here a is the type for which there is a binary operation.

In C #, the stimes function will look like a method of the Foo class:

 public Foo Times(int multiplier)

I called the method Times , not STimes , because I strongly suspect that the letter s in the name stimes means Semigroup . And note that this method has the same signature as the IExpression.Times method.

If you can define a universal implementation of such a function in Haskell, can you do the same in C #? In the Money class, we can implement Times using the Plus method:

 public IExpression Times(int multiplier) { return Enumerable .Repeat((IExpression)this, multiplier) .Aggregate((x, y) => x.Plus(y)); }

The static LINQ library's Repeat method returns this as many times as specified in the multiplier . The return value is an Enumerable<IExpression> , but according to the IExpression interface, IExpression should return one IExpression value. We use the Aggregate method to repeatedly merge two IExpression values ​​( x and y ) into one using the Plus method.

This implementation is unlikely to be as effective as the previous, concrete implementation, but here we are not talking about efficiency, but about a common, reusable abstraction. Exactly the same implementation can be used for the Sum.Times method:

 public IExpression Times(int multiplier) { return Enumerable .Repeat((IExpression)this, multiplier) .Aggregate((x, y) => x.Plus(y)); }

This is the exact same code as for Money.Times . You can also copy and paste this code into PlusIdentity.Times , but I will not repeat it here because it is the same code as above.

This means that you can remove the Times method from IExpression :

 public interface IExpression { Money Reduce(Bank bank, string to); IExpression Plus(IExpression addend); }

instead, by implementing it as an extension method :

 public static class Expression { public static IExpression Times(this IExpression exp, int multiplier) { return Enumerable .Repeat(exp, multiplier) .Aggregate((x, y) => x.Plus(y)); } }

This will work because any IExpression object has a Plus method.

As I said, this will probably be less effective than specialized implementations of The Times . In Haskell, this is eliminated by including stimes in the type class ( typeclass ), so developers can implement a more efficient algorithm than the default implementation. In C #, the same effect can be achieved by reorganizing IExpression into an abstract base class using the Times as a public virtual (overridable) method.

Validation check


Since Haskell has a more formal definition of a monoid, we can try to rewrite the Kent Beck API in Haskell, simply as proof of the idea itself. In my last modification, my fork in C # has three implementations of IExpression :


Since the interfaces are extensible, we need to take care of this, so in Haskell it seems to me safer to implement these three subtypes as a type of sum :

 data Expression = Money { amount :: Int, currency :: String } | Sum { augend :: Expression, addend :: Expression } | MoneyIdentity deriving (Show)

More formally, we can do this using Monoid

 instance Monoid Expression where mempty = MoneyIdentity mappend MoneyIdentity y = y mappend x MoneyIdentity = x mappend xy = Sum xy

The Plus method from our C # example here is represented by the mappend function. The only remaining member of the IExpression class is the Reduce method, which can be implemented as follows:

 import Data.Map.Strict (Map, (!)) reduce :: Ord a => Map (String, a) Int -> a -> Expression -> Int reduce bank to (Money amt cur) = amt `div` rate where rate = bank ! (cur, to) reduce bank to (Sum xy) = reduce bank to x + reduce bank to y reduce _ _ MoneyIdentity = 0

The rest of the timeclass mechanism will take care of the rest, so now we can reproduce one of the Kent Beck tests as follows:

 λ> let bank = fromList [(("CHF","USD"),2), (("USD", "USD"),1)] λ> let sum = stimesMonoid 2 $ MoneyPort.Sum (Money 5 "USD") (Money 10 "CHF") λ> reduce bank "USD" sum 20

Just as stimes works for any Semigroup , stimesMonoid defined for any Monoid , and therefore we can also use it with Expression .

With a historical exchange rate of 2: 1, "5 dollars + 10 Swiss francs multiplied by 2" will be just 20 dollars.

Summary


In the 17th chapter of his book, Kent Beck describes how he repeatedly tried to come up with various variants of the Money API before trying to make it “on expressions”, which he eventually used in the book. In other words, he had a lot of experience, both with this particular problem and with programming as a whole. Obviously, this work was done by a highly qualified programmer.

And it seemed to me curious that he seems to intuitively come to "monoid design." Perhaps he did it on purpose (he does not speak about it in the book), so I would rather assume that he came to this design simply because he realized its superiority. It is for this reason that it seems to me interesting to consider this particular example as a monoid, because it gives an idea that there is something highly understandable with regard to API based on a monoid. Conceptually, this is just a “small addition.”

In this article, we returned to the code of nine-year-old (actually, 15-year-old) note to identify it as a monoid. In the next article, I'm going to review the code for 2015.

Conclusion


This concludes this article. There is still a lot of information ahead that will be published in the same way as in the original - in the form of consecutive posts on Habré, linked by backward links. Here and below: originals of articles - Mark Seemann 2017, translations are made by the java-community, the translator is Yevgeny Fedorov.

Source: https://habr.com/ru/post/341398/

More articles:


All Articles