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 Arrays 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 Arrays:

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.



Thanks to Stephen Celis for reading a draft of this article.