Modularize your code with folding and monoids

Photo by Paul Teysen on Unsplash

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!

Problem

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€

Starting point

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

Initial solution. Full code: https://github.com/mgryszko/pos-folding-monoids/tree/starting-point

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:

Verbose folding over articles

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 foldLeft/foldRight/fold, Kotlin as fold, Java as reduce/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:

Fold over arbitrary articles. Full code for this iteration: https://github.com/mgryszko/pos-folding-monoids/tree/fold-over-articles

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

We’ll expand Pricing in the private total function calculating the price for a single article:

private def total(quantity: Int, tierPrice: TierPrice, unitPrice: UnitPrice): BigDecimal

TierPrice, 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.

Tier and unit price calculations are split into two visual blocks

Pricing functions

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.

Extract pricing functions for tier and unit prices

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.

Fold over pricing functions

Context-independent pricers

Our code is getting in shape (we’re folding!), but there are still unsolved issues:

• priceByTier and priceByUnit depend on total function parameters
• total accepts 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:

Total price calculation with folding over articles and pricing functions. Full code for this iteration at https://github.com/mgryszko/pos-folding-monoids/tree/fold-over-pricers

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 value1 plus value2 should equal to value2 plus 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 (BigDecimal). 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):

• Replace BigDecimal with a type variable A
• Parameterize Pricer alias, total functions and pricing functions with the type variable A instead of BigDecimal (aliased as Amount)
• Specify that there should be a Monoid instance for A with the context bound A: Monoid. This will add an implicit parameter with Monoid[A] type to total functions
• Replace BigDecimal(0) with Monoid[A].empty and + with |+| to add amounts (there are Cats imports enabling this syntax)
• Replace amount by quantity multiplication with combineN

Our test automagically continue passing! 🎉 This is thanks to cats.kernel.Monoid import which brings an implicit Monoid instance for BigDecimal.

Calculate total price with any amount type as long as there is a Monoid implementation for that type

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.

Monoid instance for FastMoney

We’ll prove that the monoid laws hold:

Prove that monoid laws hold for FastMoney

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

Summary

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/