The Algebra of Predicates and Sorting Functions
In the article “Algebraic Structure and Protocols” we described how to use Swift protocols to describe some basic algebraic structures, such as semigroups and monoids, provided some simple examples, and then provided constructions to build new instances from existing. Here we apply those ideas to the concrete ideas of predicates and sorting functions, and show how they build a wonderful little algebra that is quite expressive.
Recall from last time…
…that we defined a semigroup and monoid as protocols satisfying some axioms:
infix operator <>: AdditionPrecedence
protocol Semigroup {
// **AXIOM** Associativity
// For all a, b, c in Self:
// a <> (b <> c) == (a <> b) <> c
static func <> (lhs: Self, rhs: Self) -> Self
}
protocol Monoid: Semigroup {
// **AXIOM** Identity
// For all a in Self:
// a <> e == e <> a == a
static var e: Self { get }
}
Types that conform to these protocols have some of the simplest forms of computation around. They know how to take two values of the type, and combine them into a single value. We know of quite a few types that are monoids:
extension Bool: Monoid {
static func <>(lhs: Bool, rhs: Bool) -> Bool {
return lhs && rhs
}
static let e = true
}
extension Int: Monoid {
static func <>(lhs: Int, rhs: Int) -> Int {
return lhs + rhs
}
static let e = 0
}
extension String: Monoid {
static func <>(lhs: String, rhs: String) -> String {
return lhs + rhs
}
static let e = ""
}
extension Array: Monoid {
static func <>(lhs: Array, rhs: Array) -> Array {
return lhs + rhs
}
static var e: Array { return [] }
// ^-- Static properties are not allowed on generics in
// Swift 3.1, so we must store it as a computed variable.
}
This allows us to abstract the idea of computation (two things combining into one) so that we can focus on structure instead of details:
1 <> 2 <> 3 // => 6
"foo" <> "bar" // => "foobar"
[1, 3, 5] <> [2, 4, 6] // => [1, 3, 5, 2, 4, 6]
We were even able to write a form of reduce
for monoids that didn’t need to take an initial value or accumulator because those concepts are already built into a monoid:
func concat <M: Monoid> (_ xs: [M]) -> M {
return xs.reduce(M.e, <>)
}
concat([1, 2, 3]) // => 6
concat(["foo", "bar"]) // => "foobar"
concat([[1, 3, 5], [2, 4, 6]]) // => [1, 3, 5, 2, 4, 6]
Constructing new monoids from old
In the exercises of the last article we encouraged the reader to play with some constructions that create new monoids from existing ones. For example, the set of all functions from a fixed type into a monoid can be expressed as:
struct FunctionM<A, M: Monoid> {
let call: (A) -> M
}
This can be naturally made into a monoid:
extension FunctionM: Monoid {
static func <>(lhs: FunctionM, rhs: FunctionM) -> FunctionM {
return FunctionM { x in
return lhs.call(x) <> rhs.call(x)
}
}
static var e: FunctionM {
return FunctionM { _ in M.e }
}
}
In words, the computation f <> g
of two functions f, g: (A) -> M
produces a third function (A) -> M
by mapping a value a: A
into two values f(a)
, g(a)
in M
, and then we combine them f(a) <> g(a)
. We call this the point-wise combining of f
and g
.
Predicates
The FunctionM
construction pops up quite a bit in computer science. For example, functions of the form (A) -> Bool
are called predicates, and they are precisely the functions you give to filter
in order to obtain a subset of elements satisfying the predicate:
let isEven = { $0 % 2 == 0 }
Array(0...10).filter(isEven) // => [0, 2, 4, 6, 8, 10]
However, we saw that Bool
is a monoid with &&
as its operation and true
as its identity. This means that FunctionM<A, Bool>
is also a monoid. We can use Swift’s generic typealiases to give a name to this:
typealias Predicate<A> = FunctionM<A, Bool>
Then constructing predicate instances can be done with:
let isLessThan10 = Predicate { $0 < 10 }
let isEven = Predicate { $0 % 2 == 0 }
Using the monoid operation to combine the predicates produces a new predicate which tests for integers less than 10 and even:
let isLessThan10AndEven = isLessThan10 <> isEven
Note that we did not have to define <>
for predicates. We got it for free by the fact that Predicate
is automatically a Monoid
.
Recall that FunctionM
has a call
field for getting access to the underlying function the type represents and that Predicate
is just a specialization of FunctionM
, therefore Predicate
similarly has a call
field. That function is what can be used with Array
s filter
method:
Array(0...100).filter(isLessThan10AndEven.call) // => [0, 2, 4, 6, 8]
That doesn’t look as nice as it could if Array
had first class support for Predicate
. Fortunately, we can add it!
extension Array {
func filtered(by predicate: Predicate<Element>) -> Array {
return self.filter(predicate.call)
}
}
Note that this filtered(by:)
method could also be defined on the more general Sequence
with minimal extra effort (see the exercises).
Now we can use Predicate
more naturally with Array
s:
Array(0...100).filtered(by: isLessThan10AndEven) // => [0, 2, 4, 6, 8]
In fact, this first class support for Predicate
means there’s no reason to define one-off compositions of small predicates as we might as well use them inline:
Array(0...100).filtered(by: isLessThan10 <> isEven)
Further, we can create even smaller atomic units of predicates and have lots of flexibility in how we choose to compose them. We could have a function isLessThan
that takes a x: Comparable
value and produces a Predicate
of all values less than x
:
func isLessThan <C: Comparable> (_ x: C) -> Predicate<C> {
return Predicate { $0 < x }
}
Array(0...100)
.filtered(by: isLessThan(10) <> isEven) // => [0, 2, 4, 6, 8]
["foo", "bar", "baz", "qux"].filtered(by: isLessThan("f")) // => ["bar", "baz"]
Sorting functions
Functions that are used to sort collections also fit into this framework in a really beautiful way. To get there, we first need to define a very simple type:
enum Ordering {
case lt
case eq
case gt
}
This type encapsulates the ideas of “less than”, “equal” and “greater than”. We can turn it into a monoid quite simply, but unfortunately it takes some malice aforethought to get it right, so hopefully it will become clear to the reader soon:
extension Ordering: Monoid {
static func <>(lhs: Ordering, rhs: Ordering) -> Ordering {
switch (lhs, rhs) {
case (.lt, _): return .lt
case (.gt, _): return .gt
case (.eq, _): return rhs
}
}
static let e = Ordering.eq
}
Functions of the form (A, A) -> Ordering
are precisely the types of functions that allow us to sort collections of values of A
, for they map pairs (lhs, rhs)
to .lt
, .gt
and .eq
values to describe the order lhs
and rhs
are currently in. A sorting algorithm can use those values to figure out how to rearrange the values in a collection. Since Ordering
is a monoid, the type of functions (A, A) -> Ordering
is also a monoid, which is precisely FunctionM<(A, A), Ordering>
. We give this the name Comparator<A>
and define it with a typealias:
typealias Comparator<A> = FunctionM<(A, A), Ordering>
It is easy enough to cook up instances of comparators:
let intComparator = Comparator<Int> { lhs, rhs in
lhs < rhs ? .lt : lhs > rhs ? .gt : .eq
}
let stringComparator = Comparator<String> { lhs, rhs in
lhs < rhs ? .lt : lhs > rhs ? .gt : .eq
}
More generally, anything conforming to Comparable
can be used to derive a comparator:
extension Comparable {
static func comparator() -> Comparator<Self> {
return Comparator.init { lhs, rhs in
lhs < rhs ? .lt : lhs > rhs ? .gt : .eq
}
}
}
Int.comparator()
String.comparator()
We can make use of comparators by extending Array
so that it understands how to use them:
extension Array {
func sorted(by comparator: Comparator<Element>) -> Array {
return self.sorted { comparator.call($0, $1) == .lt }
}
}
[4, 6, 2, 8, 1, 2].sorted(by: Int.comparator())
This works, but it isn’t too impressive. We aren’t using the monoid structure on Comparator
at all yet. To do that, let’s cook up a more interesting sorting challenge. Consider the following model:
struct User {
let id: Int
let firstName: String
let lastName: String
}
We want to sort an array of users [User]
first by their last name, then first name, and then finally to ensure a well-defined sorting of the array we will sort by id
just in case two users have the exact same name. To begin we define a few basic comparators to help us out:
let idComparator = Comparator<User> {
Int.comparator().call($0.id, $1.id)
}
let firstNameComparator = Comparator<User> {
String.comparator().call($0.firstName, $1.firstName)
}
let lastNameComparator = Comparator<User> {
String.comparator().call($0.lastName, $1.lastName)
}
These can be combined together to build the comparator we previously described. To test it out, we build a large array of users and sort it:
let users = [
User(id: 1, firstName: "Denuy", lastName: "Mosler"),
User(id: 2, firstName: "Daror", lastName: "Achia"),
User(id: 3, firstName: "Achyk", lastName: "Echsold"),
User(id: 4, firstName: "Ightrayu", lastName: "Rylye"),
User(id: 6, firstName: "Umath", lastName: "Achia"),
User(id: 9, firstName: "Rakgeng", lastName: "Worirr"),
User(id: 11, firstName: "Ightrayu", lastName: "Rylye")
]
users.sorted(by: lastNameComparator <> firstNameComparator <> idComparator)
// => [ {id 2, firstName "Daror", lastName "Achia"},
// {id 6, firstName "Umath", lastName "Achia"},
// {id 3, firstName "Achyk", lastName "Echsold"},
// {id 1, firstName "Denuy", lastName "Mosler"},
// {id 4, firstName "Ightrayu", lastName "Rylye"},
// {id 11, firstName "Ightrayu", lastName "Rylye"},
// {id 9, firstName "Rakgeng", lastName "Worirr"} ]
If you look closely you’ll notice that the array is sorted first by last name, and then in the places there are equal last names it will be sorted by first name, and finally in the one instance there are equal names (“Ightrayu Rylye”) it is sorted by id
.
You can also imagine that there is a interface that allows a user to specify any number of sorts, which you could accommodate by using an array of sorts. Then you can use the concat
function to apply all of the sorts at once:
let sorts = [
lastNameComparator,
firstNameComparator,
idComparator
]
users.sorted(by: concat(sorts))
Conclusion
By starting with the simplest idea of computation, the monoid, we were able to derive an expressive algebra of predicates and sorting functions. This is largely possible due to the simplicity of monoids since it leaves a lot of wiggle room for opportunities of composition in places we might not expect. In the exercises you will dig a little deeper into this topic by constructing more operators on predicates and comparators, ending in a general construction for inducing monoid morphisms.
In a future article we will show how these ideas can be extended even further. One example is thinking of Bool
as not only a monoid but a semiring: a structure that combines the conjuctive (&&
) and disjunctive (||
) aspects of Bool
into one object. Another example is using lenses to induce comparators for free by leveraging the getters you already have.
Exercises:
1.) Define filtered(by:)
on the more generic Sequence
type.
2.) Define sorted(by:)
on the more generic Sequence
type.
3.) Define the function not<A>: Predicate<A> -> Predicate<A>
that reverses a predicate:
4.) Define the functions isGreaterThan
, isLessThanOrEqualTo
, isGreaterThanOrEqualTo
for generating predicates on a comparable, similarly to how we defined isLessThan
.
5.) Define the function isEqualTo
for generating predicates on an equatable.
6.) Define a method reversed() -> Ordering
on Ordering
that does the most sensible thing you can think of (hint: the name is telling).
7.) The method reversed
in the previous exercise is not simply any old function. It is known as a “monoid morphism” because it preserves the monoidal structure of Ordering
, i.e. (a <> b).reversed() == a.reversed() <> b.reversed()
for all a
and b
in Ordering
. Verify this in code by looping over all combinations of a
and b
and checking the equality.
8.) Define a method reversed() -> Comparator
on Comparator
by using the reversed()
method above. What does it represent? Note: Due to a limitation of Swift 3.1 you cannot extend Comparator
directly. Instead, define the method on:
extension FunctionM where M == Ordering {
func reversed() -> FunctionM {
// implementation
}
}
9.) Generalizing exercises #6-8 we can define the type of morphisms between monoids:
struct MorphismM<M: Monoid, N: Monoid> {
// AXIOM: call(a <> b) == call(a) <> call(b)
let call: (M) -> N
}
Any morphism of monoids can be used to induce a morphism on the corresponding monoid of functions. Show this by implementing the function:
extension FunctionM {
func induced<N: Monoid>(_ morphism: MorphismM<M, N>) -> FunctionM<A, N> {
// implementation
}
}
Use this construction to show how reversed
on Comparator
could have been induced by reversed
on Ordering
. Further, the not
transformation on Predicate
could have been induced by negation on Bool
.