Your iOS Home Screen is a Monoid - Part 2
by Tomás Ruiz López- •
- September 16, 2020
- •
- swift• functional programming• bow
- |
- 13 minutes to read.
In the first installment of this series, we introduced the concept of Monoid, and illustrated it with an example showing how we can combine elements on our iOS Home Screen. We covered that a Monoid provides both a combine operation, to mix two values into a new one of the same type, and a special empty value.
We modeled our problem domain using algebraic data types: a home screen item can be an empty space, a single application, or a group with at least one app; therefore, we can model this as the sum type of these three cases. Then using the protocol extension mechanisms in Swift, we made it conform to Semigroup and Monoid.
Nevertheless, there was an important piece we skipped. Semigroup and Monoid describe a set of requirements that we must implement, in the form of methods or computed variables that we have to provide in our type. But we cannot provide any implementation we would like; our implementation must obey some laws to guarantee a correct reasoning when working with these abstractions. Let’s dive into what the Semigroup and Monoid laws are, and how we can enforce them in our implementation.
Semigroup and Monoid Laws
As we mentioned in the previous post, Semigroup only has a combine operation. Our implementation of the combine function must guarantee that, given any three values of the conforming type, combining them as:
a.combine(b).combine(c)
Should yield the same result as:
a.combine(b.combine(c))
That is, we can first combine a and b, and later c, or we could first combine b and c, and later combine a with the result, and we should obtain the same result in both cases. This means our implementation of combine must be associative. This is the only Semigroup law that we must obey.
Now, when Monoids come into play, they add the notion of an empty value to the combination process. This is a special value in our type that, when combined with others, must yield the other value, unmodified. That is:
a.combine(Self.empty()) == a
Self.empty().combine(a) == a
These two properties are known as right identity and left identity. One important aspect to point out is that the implementation of a Semigroup or Monoid is not necessarily commutative, even though we can commute the empty value and get the same result. That is, combining a with b may not be the same as combining b with a.
Enforcing laws with Property-based Testing
Now that we know the properties that our implementation must have, let’s think about how we can ensure this actually happens. This type of relationship between values and functions of a certain protocol cannot be described using the type system. Rather, we need an alternative way of verifying our implementation satisfies these laws.
We can resort to testing, but the typical testing techniques we use only let us check that the properties are met for specific values. This introduces a bias in our testing, as we may be only checking the cases that actually fulfill the properties. If we want to guarantee the properties are satisfied for any possible value, we need to find a different testing technique.
This is when Property-based Testing can help. PBT is a style of testing where we can describe general properties of our code, and they will be verified with big sets of values of our types. Even though we are not testing properties for all possible values, if we take a big, random sample, our confidence in the satisfaction of the property increases. Moreover, every time we test the property, it will be tested against a different random set of inputs, providing even more confidence.
Semigroup and Monoid laws can be expressed as properties. In Swift, there is a fantastic library called SwiftCheck, inspired by the Haskell Library QuickCheck. Using SwiftCheck, we can describe the associativity property as:
property("Associativity") <- forAll { (a: A, b: A, c: A) in
a.combine(b).combine(c) == a.combine(b.combine(c))
}
This property will generate three random values of type A, and test that combining them works in an associative manner. Likewise, we can describe the identity laws:
property("Left identity") <- forAll { (a: A) in
A.empty().combine(a) == a
}
property("Right identity") <- forAll { (a: A) in
a.combine(A.empty()) == a
}
These properties can be included in a test and verified every time we run them against a different set of data. Fortunately, you don’t need to write them yourself; Bow provides a module, called BowLaws, where these and other laws are provided. If you want to read more about how to test different laws for you code, you can read the Bow documentation.
Generating random inputs
A key aspect in PBT, besides writing properties, is being able to generate random inputs to feed the properties. This means you will have to provide a way of creating different values for your types in order to be able to test the Semigroup and Monoid laws.
In order to do this, SwiftCheck provides the Arbitrary protocol. This protocol requires you to provide a generator for your type, represented by the Gen<A> type. Plain types, like Int or String, already include an implementation of the Arbitrary protocol that generates values of those types with no restrictions. If we want to modify such generators, we can use powerful functional combinators to apply transformations to their outputs.
For instance, we will need to generate names for our apps and titles for our groups, and we would like those strings not to be empty. We can create an extension for a custom String generator that ensures it won’t generate empty strings. We can do it by filtering outputs using the suchThat method:
extension String {
static var nonEmptyArbitrary: Gen<String> {
String.arbitrary.suchThat(not <<< \.isEmpty)
}
}
This implementation is particularly interesting. We start with the general string generator String.arbitrary, which is transformed using suchThat. Then, we use point-free composition with the <<< operator, which lets us compose two functions. These two functions are not, which is a function included in Bow that wraps the ! operator; and \.isEmpty, which is a key path over the same name property that, thanks to a recently included evolution proposal in Swift, lets us use key paths as functions. The result of composing these two functions is a new function that is provided to suchThat, filtering out empty strings from the generation process.
This new generator can help us add conformance to Arbitrary for our App model. We can start with the non-empty generator, and then embed this result into an App by mapping it with the initializer:
extension App: Arbitrary {
public static var arbitrary: Gen<App> {
String.nonEmptyArbitrary.map(App.init)
}
}
Finally, we can add conformance to Arbitrary for HomeScreenItem. However, this could be a bit more complex, as we have three cases that contain different data structures. Let’s break down the implementation. First, we start by conforming to the protocol using the extension mechanisms:
extension HomeScreenItem: Arbitrary {
public static var arbitrary: Gen<HomeScreenItem> {
// Your implementation goes here
}
}
Then, we can create three generators, one for each case inside the enum. The most straightforward one is the one corresponding to the empty case. There is a single value we can provide in the generation process, so we can lift it into a generator using pure:
let nothingGen = Gen<HomeScreenItem>.pure(.nothing)
Our second case corresponds to having a single app. We can start with the generator we just implemented for App, and then embed it into the corresponding case of HomeScreenItem using map:
let singleGen = App.arbitrary.map(HomeScreenItem.single)
Then, the third case requires us to create a group, where we need a non-empty array of apps, and a title. This means we need to somehow combine the generators for NEA and String. In order to obtain a generator for NEA, Bow provides a module called BowGenerators, where we can get conformance to Arbitrary for every possible type included in the library. Then, to combine two (or more) independent generators into a tuple, we can use zip; and finally we can map to the corresponding enum case:
let groupGen = Gen.zip(
NEA<App>.arbitrary,
String.nonEmptyArbitrary
).map(HomeScreenItem.group)
Now that we have three generators, one for each case, we need to combine them into a single one that is able to randomly choose among them. To do so, we can use the one(of:) method:
return Gen.one(of: [nothingGen, singleGen, groupGen])
The complete implementation for this conformance is:
extension HomeScreenItem: Arbitrary {
public static var arbitrary: Gen<HomeScreenItem> {
let nothingGen = Gen<HomeScreenItem>.pure(.nothing)
let singleGen = App.arbitrary.map(HomeScreenItem.single)
let groupGen = Gen.zip(
NEA<App>.arbitrary,
String.nonEmptyArbitrary
).map(HomeScreenItem.group)
return Gen.one(of: [nothingGen, singleGen, groupGen])
}
}
Testing the laws
Now that we have our generators, testing the laws for Semigroup and Monoid is trivial. We just need to import BowLaws and invoke the laws with our implementing type:
func testSemigroupLaws() {
SemigroupLaws<HomeScreenItem>.check()
}
func testMonoidLaws() {
MonoidLaws<HomeScreenItem>.check()
}
If our Semigroup and Monoid implementations are correct, these tests will pass. Otherwise, we will get a counterexample that made the properties fail. We can use this counterexample to know why our implementation failed. Moreover, we can get the initial seed used in the random generation of our input, so that we can recreate the same scenario that made our property fail, and check if our changes actually fix the problem. For more information about this, please refer to the library documentation.
An important aspect that we didn’t explain in the previous post was why we were using an empty string when we create a new group, and why we decide to concatenate the names of two groups when combining them. As you may guess, String is also a Monoid, where the combination of Strings is the concatenation, and the empty value is the empty String. As titles are part of our structure, if we want to satisfy our type’s monoidal properties, we need to use the same combination and empty element that we use in the String Monoid. As an exercise, try to modify the way titles are created or combined, and check that the laws do not apply anymore. Seeing counterexamples of it will help you understand the implementation.
Conclusion
Semigroups and Monoids are structures that go beyond typical examples involving numbers, strings, or arrays. Discovering these structures in your domain models can provide additional benefits; for instance, knowing the laws that govern combination, you can reorder how things are combined into a way that is more performant, without altering the behavior of the program. Don’t be scared by the terminology, as the concepts behind it are pretty simple and universal, and once you get familiar with them, you’ll be able to use them in any platform, language, or library.
You can check the full implementation for these series in this repository.
Please check out the following Bow resources. Comments and questions are welcome and encouraged!
Bow, and its ecosystem, is proudly sponsored by 47 Degrees, a Functional Programming consultancy with a focus on the Scala, Kotlin, Swift, and Haskell Programming languages supporting the active development of Bow.