# Semirings and Predicates

In the article “The Algebra of Predicates and Sorting Functions” we showed how predicates can be made into a monoid. In short, we considered `Bool`

to be a monoid with its operation given by `&&`

and identity `true`

, and then defined `Predicate<A>`

to be the type of functions `(A) -> Bool`

. This allowed us to combine predicates in an expressive way, e.g. `isEven <> isLessThan(10)`

is the predicate that literally expresses “is even and is less than 10”.

One thing missing from that discussion is that `Bool`

has another monoidal structure, `||`

with `false`

. We will discuss how to rectify that in detail by defining something called a *semiring*.

Download a playground of the code in this article to follow along at home!

## A tale of two monoids

First recall that a monoid is a type conforming to a protocol that specifies an associative binary operation and an identity element:

```
protocol Monoid {
// **AXIOM** Associativity
// For all a, b, c in Self:
// a <> (b <> c) == (a <> b) <> c
static func <> (lhs: Self, rhs: Self) -> Self
// **AXIOM** Identity
// For all a in Self:
// a <> e == e <> a == a
static var e: Self { get }
}
```

The `Bool`

type naturally has two monoidal structures: one defined by `(&&, true)`

and the other by `(||, false)`

. Neither of those is the *right* one, or more important than the other, yet Swift’s protocols force us to choose one for `Bool`

(as do most programming languages out there!). One way around this is to wrap `Bool`

in another type so that we can conform it to the protocol without interfering with `Bool`

:

```
struct AndBool: Monoid {
let value: Bool
init(_ value: Bool) { self.value = value }
static let e = AndBool(true)
static func <> (lhs: AndBool, rhs: AndBool) -> AndBool {
return .init(lhs.value && rhs.value)
}
}
struct OrBool: Monoid {
let value: Bool
init(_ value: Bool) { self.value = value }
static let e = OrBool(false)
static func <> (lhs: OrBool, rhs: OrBool) -> OrBool {
return .init(lhs.value || rhs.value)
}
}
```

We now have two different versions of booleans: one that is a monoid under conjunction `&&`

and the other under disjunction `||`

. However, many times you don’t want to separate the ideas of `&&`

and `||`

from `Bool`

, but instead have one underlying structure that unifies them. This structure is called a *semiring*.

## Semirings

A semiring is much like a monoid, but it has an additional operation on it, and the operations must play “nicely” together. Formally, a semiring is a type with two operations, denoted by `+`

and `*`

, and two distinguished elements `zero`

and `one`

as identities, satisfying a bunch of axioms:

```
protocol Semiring {
// **AXIOMS**
//
// Associativity:
// a + (b + c) == (a + b) + c
// a * (b * c) == (a * b) * c
//
// Identity:
// a + zero == zero + a == a
// a * one == one * a == a
//
// Commutativity of +:
// a + b == b + a
//
// Distributivity:
// a * (b + c) == a * b + a * c
// (a + b) * c == a * c + b * c
//
// Annihilation by zero:
// a * zero == zero * a == zero
//
static func + (lhs: Self, rhs: Self) -> Self
static func * (lhs: Self, rhs: Self) -> Self
static var zero: Self { get }
static var one: Self { get }
}
```

A (perhaps) shorter way to say the same thing is that 1.) `S`

is a commutative monoid with `(+, zero)`

, 2.) a monoid with `(*, one)`

, 3.) `*`

distributes over `+`

, and 4.) `zero`

annihilates with `*`

.

We can now turn `Bool`

into a semiring:

```
extension Bool: Semiring {
static func + (lhs: Bool, rhs: Bool) -> Bool {
return lhs || rhs
}
static func * (lhs: Bool, rhs: Bool) -> Bool {
return lhs && rhs
}
static let zero = false
static let one = true
}
```

It may seem weird to define `+`

and `*`

on `Bool`

, but `||`

and `&&`

really do behave like addition in multiplication since this distributivity property holds:

```
a && (b || c) == a && b || a && c
a * (b + c) == a * b + a * c
```

## Constructing new semirings from existing

Many of the constructions we did for monoids also work for semirings. For example, we can take the type of functions from a fixed type into a semiring:

```
struct FunctionS<A, S: Semiring> {
let call: (A) -> S
}
```

This type also naturally forms a semiring by performing the operations point-wise:

```
extension FunctionS: Semiring {
static func + (lhs: FunctionS, rhs: FunctionS) -> FunctionS {
return FunctionS { lhs.call($0) + rhs.call($0) }
}
static func * (lhs: FunctionS, rhs: FunctionS) -> FunctionS {
return FunctionS { lhs.call($0) * rhs.call($0) }
}
static var zero: FunctionS {
return FunctionS { _ in S.zero }
}
static var one: FunctionS {
return FunctionS { _ in S.one }
}
}
```

## A better definition of predicate

Rather than defining `Predicate`

as the monoid of functions `(A) -> Bool`

, we are going to defined as the semiring of functions `(A) -> Bool`

:

```
typealias Predicate<A> = FunctionS<A, Bool>
```

And we can make Swift’s standard library understand these predicates by extending `Sequence`

:

```
extension Sequence {
func filtered(by p: Predicate<Element>) -> [Element] {
return self.filter(p.call)
}
}
```

Now we can combine predicates using both conjunctive and disjunctive operations and apply it to sequences:

```
let isEven = Predicate<Int> { $0 % 2 == 0 }
let isLessThan = { max in Predicate<Int> { $0 < max } }
let isMagic = Predicate<Int> { $0 == 13 }
Array(0...100).filtered(by: isEven * isLessThan(10) + isMagic)
```

This last expression describes getting only the integers from `0`

to `100`

that are even and less than 10, *or* are the magic number. It reads quite nicely, but it would be even better if we could use `||`

and `&&`

, so let’s define them!

```
func || <A> (lhs: Predicate<A>, rhs: Predicate<A>) -> Predicate<A> {
return lhs + rhs
}
func && <A> (lhs: Predicate<A>, rhs: Predicate<A>) -> Predicate<A> {
return lhs * rhs
}
```

Now we can write:

```
Array(0...100).filtered(by: isEven && isLessThan(10) || isMagic)
```

And now that reads great! We can even take it a step further by defining a prefix function `!`

for negating a predicate:

```
prefix func ! <A> (p: Predicate<A>) -> Predicate<A> {
return .init { !p.call($0) }
}
Array(0...100).filtered(by: isEven && !isLessThan(10) || isMagic)
```

## Conclusion

We have now seen how sometimes when a type seems to have two different monoidal structures on it, secretly it may be a semiring where the two structures play nicely together! There can still be times where a type has two different monoidal structures on it such that they do not form a semiring, in which case you must resort to wrapping the type in a new type that provides the custom conformance.

## Exercises

1.) Previously we defined a `concat`

function

```
func concat <M: Monoid> (_ xs: [M]) -> M {
return xs.reduce(M.e, <>)
}
```

that concatenates an array of monoidal values into a single one by `<>`

’ing them together. Semirings have two versions of this, so define em!

```
func add<S: Semiring>(_ xs: [S]) -> S {
???
}
func multiply<S: Semiring>(_ xs: [S]) -> S {
???
}
```

2.) A semiring `(S, +, *, zero, one)`

naturally induces two different monoids, `(S, +, zero)`

and `(S, *, one)`

, where you “forget“ one of the operations. The former is even a commutative monoid. Make two new types `AdditiveMonoid<S: Semiring>`

and `MultiplicativeMonoid<S: Semiring>`

that converts a semiring to its monoid form.

3.) Recall that a “commutative monoid” is a monoid `A`

in which `a <> b = b <> a`

for all `a, b: A`

. Show that

```
struct EndoS<A: CommutativeMonoid> {
let call: (A) -> A
}
```

is a semiring where `+`

is given by pointwise `<>`

-application of functions and `*`

is given by function composition.

4.) A ring is a semiring that has the additional axiom that addition is invertible, i.e. there is a function `inverse: (S) -> S`

such that `a + inverse(a) = inverse(a) + a = S.zero`

for all `a: S`

. Can you think of anything that form a ring? Does `Bool`

form a ring?