In the article “Algebraic Structure and Protocols” we explored the idea of abstracting algebraic properties of types through protocols. Exercises were provided at the end in order to delve deeper into the topic. Here we present some solutions

1.) In order to make enum Empty {} (the enum with no values) into a semigroup we must define the operation:

extension Empty: Semigroup {
  func op(_ b: Empty) -> Empty {
    // ???
  }
}

Now, Empty contains no values, hence b: Empty is impossible to construct, but a function Empty -> Empty can be constructed (c.f. the solution to #8 in “Proof in Functions”). There are two ways to implement op: we can return self or we can return b. They both satisfy the compiler and the semigroup axioms, and both options give equivalent definitions of the same semigroup:

extension Empty: Semigroup {
  func op(_ b: Empty) -> Empty {
    return self // could also return `b`
  }
}

The empty enum cannot be made into a monoid because a monoid requires an identity element e: Empty. No values can be constructed in `Empty, hence it cannot be a monoid.

The empty semigroup may sound pathological, but allowing it can simplify some theories by giving us access to certain universal constructions.

2.) The empty struct struct Unit {} can be made into a monoid quite easily:

extension Unit: Monoid {
  func op(_ b: Unit) -> Unit {
    return self // could also return `b`
  }
  static func e() -> Unit {
    return Unit()
  }
}

This type can also be made into a group. Since the type contains only a single value we can simply make the inverse be the identity function:

extension Unit: Group {
  func inv() -> Unit {
    return self
  }
}

3.) The type M<S: Semigroup> essentially makes S into an optional type. It adjoins a new value Identity to S so that a value of M<S: Semigroup> is either of type S or that newly added value. The Optional type does the same, except the value it adjoins is called None.

4.) In order to make Endomorphism<A> into a semigroup we need to define the operation:

extension Endomorphism : Semigroup {
  func op(_ endo: Endomorphism) -> Endomorphism {
    // ???
  }
}

We need to figure out how to fill in this function. Taking inspiration from the article “Proof in Functions”, we look at the types we have at our disposal, and see how we can fit them together to get what we need. To start with, we definitely need to return something in Endomorphism, so we can fill in that part:

extension Endomorphism: Semigroup {
  func op(_ endo: Endomorphism) -> Endomorphism {
    return Endomorphism { a in
      return ???
    }
  }
}

Now we have a: A to work with, but we also have self.f: A -> A and endo.f: A -> A. Those functions compose, so we can finish this with:

extension Endomorphism: Semigroup {
  func op(_ endo: Endomorphism) -> Endomorphism {
    return Endomorphism { a in
      return self.f(endo.f(a))
    }
  }
}

To enhance this into a monoid we need to define the identity element. What’s a function such that when composed with any other function it leaves that function unchanged? None other than the identity function:

extension Endomorphism: Monoid {
  static func e() -> Endomorphism {
    return Endomorphism { a in
      return a
    }
  }
}

Now Endomorphism is a monoid. Can it be made into a group? If it could then any function f: A -> A would be invertible, i.e. we could find a g: A -> A such that their composition (in any order) is the identity function A -> A. Such a thing is clearly impossible, for example any constant function A -> A is not invertible. Therefore Endomorphism cannot be made into a group.

5.) We can make Predicate in a monoid with the following:

extension Predicate: Monoid {
  func op(_ pred: Predicate) -> Predicate {
    return Predicate { a in
      return self.p(a) && pred.p(a)
    }
  }

  static func e() -> Predicate {
    return Predicate { _ in true }
  }
}

6.) We can make FunctionM into a monoid with the following:

extension FunctionM: Monoid {
  func op(_ function: FunctionM) -> FunctionM {
    return FunctionM { x in
      return self.f(x).op(function.f(x))
    }
  }

  static func e() -> FunctionM {
    return FunctionM { _ in M.e() }
  }
}

7.) We can make FunctionG into a group with the following:

extension FunctionG: Monoid {
  func op(_ function: FunctionG) -> FunctionG {
    return FunctionM { x in
      return self.f(x).op(function.f(x))
    }
  }

  static func e() -> FunctionG {
    return FunctionM { _ in G.e() }
  }

  func inv() -> FunctionG {
    return FunctionG { x in
      return self.f(x).inv()
    }
  }
}

8.) We can make Max into a semigroup using the max function:

extension Max: Semigroup {
  func op(_ s: Max) -> Max {
    return Max(max(self.a, s.a))
  }
}

And similarly for Min:

extension Min: Semigroup {
  func op(_ s: Min) -> Min {
    return Min(min(self.a, s.a))
  }
}

We can’t make Max and Min into monoids because they don’t have an identity, i.e. there isn’t a single element that is less/greater than all comparable values.

9.) The following computations represent the max and min, respectively of the list of values:

sconcat([Max(2), Max(5), Max(100), Max(2)], Max(0))    // #=> Max(100)
sconcat([Min(2), Min(5), Min(100), Min(2)], Min(200))  // #=> Min(2)

10.) Performing the M construct on Max and Min will adjoin a new value to the types that is less/greater than any other value in Max/Min, respectively. Therefore the following computations correspond to finding the max and min values:

mconcat([M(Max(2)), M(Max(5)), M(Max(100)), M(Max(2))])  // #=> Max(100)
mconcat([M(Min(2)), M(Min(5)), M(Min(100)), M(Min(2))])  // #=> Min(2)