47 Degrees joins forces with Xebia read more

Your iOS Home Screen is a Monoid - Part 1

Your iOS Home Screen is a Monoid - Part 1

Functional Programming is based on mathematical constructions, and sometimes the terminology used may sound too academic, even esoteric. However, once the abstract pattern that those constructions model is understood, we can keep finding examples where we can use them. In fact, because abstractions are derived from mathematical principles, we get additional properties in the form of laws that drive our reasoning and can help us perform optimizations or refactorings to our code.

In this two-part post, we will be talking about Monoids, an algebraic structure that lets us combine values of a certain type in an associative manner. We will illustrate with an example that you see every day, but probably never stopped to think that it fits in this mathematical construction: your iOS Home Screen.

What is a Monoid?

A Monoid is an algebraic structure with the following properties:

  • It lets us combine two values of the same type into a new value.
  • It provides a special element called empty.

There are situations where our types can only satisfy the first property (combination) but not the second. In these cases, the algebraic structure that we have is called a Semigroup.

In Swift, we can represent these requirements as protocols. Protocols help us describe abstract operations that can be implemented by different types. Therefore, we can encode a Semigroup in Swift as:

public protocol Semigroup {
  func combine(_ other: Self) -> Self
}

That is, in order for our type to conform to Semigroup, we need to provide a function called combine that takes another value of the implementing type and combines it with the receiver. Similarly, we can encode a Monoid as:

public protocol Monoid: Semigroup {
  static func empty() -> Self
}

A Monoid extends Semigroup to ensure it gets the combine operation, and adds a static function to compute the empty value. There are other restrictions for the implementation of these protocols, which are given by the laws of Semigroup and Monoid. However, these restrictions cannot be captured in the Swift type system; rather, we need to add tests to verify our implementation conforms to these laws. We will revisit this in the following post.

Both Semigroup and Monoid are available in Bow and Bow Lite. Importing these libraries in your project will let you conform to these protocols and get additional functions for free when you implement them for your types.

An iOS Home Screen

The iOS Home Screen displays all installed apps on your iPhone or iPad as a grid. It lets you perform a long press gesture to edit it; while in this mode, app icons seem to shiver, wondering about their fate! We can drag and drop them to group different applications in folders, reducing the clutter.

We can consider this operation of dragging and dropping apps to create groups as a sort of combination of items. There are some combinations that are not allowed though; for instance, we can drag a single app onto a group, but we cannot do the opposite. Likewise, We can’t drag a group onto another group. Nonetheless, there is no reason why this should not be possible, and we will consider that all these possibilities are valid in our implementation.

But before implementing our Semigroup and Monoid conformances, we need to come up with a model for our home screen items. There are three possible things that we can have in a position in the grid:

  • A single application.
  • A group of different applications, with a title.
  • An empty space in the grid.

We can start by modeling an application. For the sake of simplicity, we will create a simple struct with the application’s name, but we could add any additional information we would like:

struct App: Equatable {
  let name: String
}

Once we have this (simple) model for an app, we can design our model for grid items. As we have listed above, we have three possible cases, with totally unrelated data. When we have this situation, we can use a sum type to put all these cases together as a single type. As we know, sum types are modeled as enums in Swift:

enum HomeScreenItem: Equatable {
  case nothing
  case single(App)
  case group(NEA<App>, title: String)
}

Notice that our group of applications is modeled using a non-empty array (NEA). This helps us capture the requirement of not having a group that does not have any apps inside. If we had modeled this using a plain array instead of using NEA, we could create an illegal value of this type as HomeScreenItem.group([], title: "Some title"). Using NEA prevents this from happening.

You may have also noticed that our models conform to Equatable. We get this conformance for free, implemented by the compiler just by looking at the structure of the type, and it will let us compare values of these types when we start testing our implementations.

Implementing Semigroup and Monoid

Now that we have a model for home screen items, we can define what it means to combine two of these items. To do so, we can use the extension mechanisms in Swift to conform to the Semigroup protocol. We can use pattern matching to address all possible combinations of the two items involved in the combination:

extension HomeScreenItem: Semigroup {
  func combine(_ other: HomeScreenItem) -> HomeScreenItem {
    switch (self, other) {
      // Add implementation here
    }
  }
}

The simplest cases we can handle correspond to combining an empty element with anything else. This would be equivalent to moving an item into an empty position, which results in having the same item:

case (_, .nothing): return self
case (.nothing, _): return other

Then, we can handle the case where we are combining two plain apps. In this case, the result should be a group with both apps. We will use an empty string as the title for this new group; we will come back to this decision in the following post, when we talk about the laws of Semigroup and Monoid.

case let (.single(left), .single(right)):
    return .group(NEA.of(left, right), title: "")

Now, we can handle combining a single app and a group of apps. Depending on the order of the combination, we can choose to prepend or append the single app in the group of apps. This models the situations of dragging a group onto a single app (where the app should be placed in the first position of the new group), or dragging a single app onto a group (where the app should be placed in the last position of the new group). In both cases, we keep the existing name of the group.

case let (.single(app), .group(nea, title: title)):
    return .group(NEA.of(app) + nea, title: title)

case let (.group(nea, title: title), .single(app)):
    return .group(nea + NEA.of(app), title: title)

Finally, it seems reasonable to think that combining two groups of apps should result in the combination of both arrays and titles of the groups.

case let (.group(left, title: leftTitle), .group(right, title: rightTitle)):
    return .group(left + right, title: leftTitle + rightTitle)

With this, we have handled all possible combinations of home screen items. This is the complete implementation of the Semigroup conformance:

extension HomeScreenItem: Semigroup {
  func combine(_ other: HomeScreenItem) -> HomeScreenItem {
    switch (self, other) {
    case (_, .nothing): return self
    case (.nothing, _): return other

    case let (.single(left), .single(right)):
      return .group(NEA.of(left, right), title: "")

    case let (.single(app), .group(nea, title: title)):
      return .group(NEA.of(app) + nea, title: title)

    case let (.group(nea, title: title), .single(app)):
      return .group(nea + NEA.of(app), title: title)

    case let (.group(left, title: leftTitle), .group(right, title: rightTitle)):
      return .group(left + right, title: leftTitle + rightTitle)
    }
  }
}

The conformance to Monoid is much simpler. We can use the extension mechanisms to conform to this protocol as well:

extension HomeScreenItem: Monoid {
  static func empty() -> HomeScreenItem {
    // ???
  }
}

We have to provide a value for this type that represents the notion of empty. This should be a value that, when combined with anything else, results in the other value, with no modifications. According to the implementation we have provided above, it seems this value is the nothing case in our home screen item.

extension HomeScreenItem: Monoid {
  static func empty() -> HomeScreenItem {
    .nothing
  }
}

Conclusion

In this post, we have explored the general notion of Semigroup and Monoid. We have illustrated these with an example that we are used to seeing every day on our devices, and we have discovered that, thinking abstractly about what it means to combine two values of a given type, we can unlock use cases that should be allowed. However, we still need to make sure our implementation is correct according to the laws that govern these algebraic structures! There are many ways of implementing the combination of these items, but not all of them are legal. Being lawful will unlock additional properties for us; we will check that in the following post.

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.

Ensure the success of your project

47 Degrees can work with you to help manage the risks of technology evolution, develop a team of top-tier engaged developers, improve productivity, lower maintenance cost, increase hardware utilization, and improve product quality; all while using the best technologies.