Modularize your code with folding and monoids
In this article, I’ll show you how to apply functional programming techniques to achieve greater abstraction and flexibility in your code. We’ll refactor together a rigid code towards a more generic solution by introducing folding (or reduce), higher-order functions, and combining values in an abstract way (with a fancy name of monoid). Let’s jump straight to the problem statement and the Scala code!
We are developing a supermarket point-of-sale. The first requirements and examples are simple:
- 🥐 croissants are sold for 1.10€ each (unit price), three for 2.65€ (tier price)
- 🥖 baguettes are sold for 0.75€ each, five for 3.00€
After some TDD cycles, we reached a solution where:
- only two fixed articles (croissants and baguettes) are supported. They are hardcoded as pricing function parameters
- every article must have both a unit and a tier price. Article quantity, unit, and tier price are the input to the pricing function
You may ask why I didn't already implement a more flexible solution supporting any number of articles and other pricing models? I strictly followed the specification with just enough code and design in red-green-refactor cycles. I was patiently waiting until new requirements emerge. And there is already a new one …
Sell bread rolls 🫓
… and possibly other articles. To speed up delivery, we negotiate with the supermarket owner that all sold articles must follow the tiered/unit pricing model.
Let’s add the third parameter
total for a bread roll pricing and make the code a bit more verbose to see if we can spot the pattern:
What we have just done? We start with a
0total, add the croissants total to it, then add the baguettes total and finally the bread rolls total. In more abstract terms, we iterate over a collection of articles, for each of them we compute its selling price, and we accumulate it with the running total. We have to specify the initial total — zero.
This is the essence of a very common pattern — fold (reduce, accumulate): go over a collection, compute a value for each element and join those values somehow (providing an initial value for the first “concatenation”). It’s widely supported in programming languages; Scala implements it for all iterable collections as
fold, Kotlin as
fold, Java as
collect on a stream.
We’ll replace specific articles with a list of arbitrary articles. Since we want to traverse them in the usual direction (from left to right), we’ll be using the
foldLeft operator. The final code for the
total function becomes fairly compact:
Now, we can price any article as long as there are defined both the tiered and the unit prices. We want to be flexible on the pricing model and …
Offer bulk prices
Moreover, we don’t want to be forced to define the unit price. Or we’d like to have only the unit price without other pricing models— we learned from the supermarket owner that this is the most common case in retail!
Can we use our fold Swiss knife to prepare our code to add the bulk pricing model? The previous refactor was just a warm-up; here we need a couple of more steps. Let’s recap which ingredients of the fold pattern we have to discover:
- a collection to go over
- an initial element
- what to pass between iterations
Inline parameter object
Pricing in the private
total function calculating the price for a single article:
private def total(quantity: Int, tierPrice: TierPrice, unitPrice: UnitPrice): BigDecimal
UnitPrice (and future pricing models) are going to be transformed into the elements of the collection. We have to wait for a little to see the collection element type emerge.
Initial value, fold operations, and accumulator
Next, We’ll expand the body of the
total function to define the initial value and the accumulator to pass between iterations. It seems obvious that we have to start with the
0 total. We need two iterations: first for the tier price, second for the unit price. When looking at the second iteration, we observe that we have to carry over the remaining quantity and the total from the first iteration — the pair of both values will be our accumulator.
As I claimed at the beginning of this article, we’re going to do FP here: we create programs by combining functions. Functions are first-class citizens and can be treated as ordinary values.
Let’s define those functions — values we’ll play with. If we want to put them in a list and fold over them, the functions must have the same shape (i.e. the same type) — same inputs and outputs. I’ll encapsulate tier and unit pricing steps (made explicit in the previous refactor) as functions taking the quantity as input and returning the remaining quantity and the price as the output. This function type:
Int -> (Int, BigDecimal) is the common denominator of both calculations. You may notice that our pricing functions need additionally some data from outside (e.g. the tier quantity), but let’s tackle this in one of the next refactors. To make the function types more readable, we’ll also introduce a couple of type aliases.
Explicit pricing steps to fold
Let’s put the recently created functions in a list, and execute them with
foldLeft to compute the grand total. In each iteration, we’ll receive a pricing function to call and the quantity. We have to return the remaining quantity and the running total to the next iteration.
Our code is getting in shape (we’re folding!), but there are still unsolved issues:
totalaccepts fixed pricing models
Both extracted functions are closures since they refer to variables in the surrounding scope. To make our code compositional and allow our callers to pass an arbitrary list of pricing functions, we have to make them dependent only on the input parameters.
How can we do this? As with every problem in computer science, by indirection. Instead of depending on the outer function parameters (from
total), we’ll create factory functions returning our pricers in the required shape (type). We’ll change the private
total function to accept a list of pricers (
Int -> (Int, BigDecimal) functions). This will require us to run our factories outside of the refactored
total. In this refactoring, we’ll take bigger steps; I’ll present here the final code for this iteration:
The technique we just applied has a name — higher-order functions. They are functions that return other functions or accept other functions as inputs. We already saw such a function —
foldLeft but I didn’t want to face you with geeky terms right at the beginning.
Multicurrency 💵 💶 💷 💴
The supermarket chain is expanding its business by creating an online platform where merchants around the world can sell their stock in any imaginable currency. The company is very happy with the pricing engine and they want to use it on the new site. How can we adapt our pricing calculation for multiple currencies with a minimum intervention?
Get away from numbers!
After looking in detail at the current code, we realize that we could represent amounts as any type as long as it supports the following operations:
- providing a zero amount
- adding two amounts
- multiplying an amount by a positive number. This is actually a special case of adding the same amount N times.
There is already such a pattern on the functional market — monoid! It provides a simple API for the operations we want to perform:
- generate zero/empty values
- add/append/combine two values
Monoid defines two basic rules every implementation should follow:
- it doesn’t matter if we add values from left to right, from the inside to outside, or from right to left (associativity)
- adding zero to a value doesn’t change that value
Keep in mind that the laws don’t say that
value2 should equal to
value1. plus/append operation is not necessarily commutative. The instance for a given type may support this, but it’s not guaranteed.
We’ll be using Cats
Monoid abstraction and implementation for the current amount type (
Monoid is a type class — a broader pattern to define an abstract behavior which may be defined for concrete types, not by concrete types. The implementation is external to the type — it allows to add new functionality without subclassing. In Scala, an instance (or an evidence) of the typeclass is provided as an implicit parameter.
To replace the concrete
BigDecimal type with any type that has a monoid instance, we need to perform the following steps (source code follows):
BigDecimalwith a type variable
totalfunctions and pricing functions with the type variable
- Specify that there should be a
Awith the context bound
A: Monoid. This will add an implicit parameter with
|+|to add amounts (there are Cats imports enabling this syntax)
- Replace amount by quantity multiplication with
Our test automagically continue passing! 🎉 This is thanks to
cats.kernel.Monoid import which brings an implicit
Monoid instance for
Make money fast
Does our promise hold that we can plug in any other type behaving like
Monoid? Let’s check it by integrating the JavaMoney library and implementing a monoid instance for the
org.javamoney.moneta.FastMoney class we’ll use as the future replacement for BigDecimal.
We’ll prove that the monoid laws hold:
The final step is to provide a
Monoid instance to
total unit tests and to adapt the mini-DSL for creating articles and amounts:
assert(total(List(3.croissants, 5.baguettes)) == "5.65".eur)
They are all passing! 🎊
You may noticed that we’re fixing the currency in the
FastMoney factory method. This is due to the fact that
FastMoney.add implementation is not a total function. Total function provides a result for all values of its inputs.
add throws an exception if addend currencies don’t match — it’s a partial function. A possible solution would be to implicitly convert monetary amounts between currencies, fixing either the left or the right addend currency as the currency for the result. Even in that case the monoid rules will hold — the addition will be still associative but not anymore commutative (as you remember from the previous section, commutativity is not required for a fully-fledged monoid).
In this imaginary code evolution I showed you how to implement a flexible solution to growing business requirements through some basic and intermediate functional programming concepts and patterns:
- Folding with functions as first-class values
- Higher-order functions
- Sum abstraction through monoid
Although they may have unfamiliar names and come with a complex math background, they are quick to master. And the most important thing — they level up modularity of your solution.
Full source code with detailed refactor steps can be found at https://github.com/mgryszko/pos-folding-monoids/