Monoid morphisms, products, and coproducts

[runarorama]

This is an issue reserved for comments on http://blog.higher-order.com/blog/2014/03/19/monoid-morphisms-products-coproducts/

[tailcalled]

A few errors: B=>B is actually bigger than B Neither These[A, B] '(which is too small) nor List[Either[A, B]] '(which is too big) form the coproduct. In particular, you are assuming that the monoid operation is commutative. The true coproduct is a list of A's and B's that alternates: type MonCoprod[A, B] = Either[Aux[A, B], Aux[B, A]] sealed trait Aux[+A, +B] case class More[A, B]'(x: A, rest: Aux[B, A]) extends Aux[A, B] case object Stop extends Aux[Nothing, Nothing]

[runarorama]

tailcalled: Thanks for the comment! How is B => B bigger than B exactly (without dropping the fact that B is a monoid)?

How is These[A,B] too small? I think I've proved that it makes the coproduct diagram commute. I am likely wrong about this, but I don't immediately see it.

I've accounted for the fact that List[Either[A,B]] is too big, with Eithers which is like you say an alternating list. Its representation is just List[Either[A,B]] but that's an implementation detail. I'm confident that this part is OK, but I'd like to correct the other two errors!

[runarorama]

OK, I see a B => B counterexample: const "foo". I could restrict the type to contain only operations in the monoid B, but that might be cheating and sort of obviously true.

[tailcalled]

Essentially, inl("a") |+| inr("b") should be different from inr("b") |+| inl("a"), since the codiagonal map should distinguish them (i.e. "ab" vs "ba"). This is not the case for These, and that actually causes your List[Either[A, B]] to be too general. To be verbose, let J be the codiagonal map (ie. from A+A to A). J(inr("b") |+| inl("a")) will then be "ab" in your implementation, but algebra says it should be different: J(inr("b") |+| inl("a")) = J(inr("b")) |+| J(inl("a")) = "b" |+| "a" = "ba"

[tailcalled]

Also, just realized that my MonCoprod is slightly too big (it is actually the free monoid (that is, Maybe/Option) of the semigroup coproduct of the underlying semigroups of the monoids). It needs to quotient the identities out, but I don't think that can be done in Scala.

[runarorama]

Yeah, I see that Both(a,b) will commute all A to the left and all B to the right. So that's clearly wrong. That's fixed now.

But I still don't see how Eithers[A,B] is too general. Note that it is not the same monoid as List[Either[A,B]]. It's essentially your MonCoprod, though admittedly the alternating nature is not advertised in the type.

[runarorama]

Won't the identities "quotient themselves out" anyway? I mean it looks like it's too big in the sense that you can always add an identity and then more list, but that doesn't seem to have any consequences.

[runarorama]

We can certainly cheat in Scala, since every type implements an equality. So we could simply ask if a given element is the identity and drop it in that case.

[ghost]

Good stuff. Is the general feel of the book more stuff like this? If it is then this would be a really nice way to learn some category theory.

[tailcalled]

Eithers is fine, except that the underlying list is accessible, which makes certain evil functions possible. After quotienting, there's nothing to worry about. Also, note that These actually only needs the Both constructor, since the sides of the product can be filled up by the monoidal identity. In fact, if one doesn't consider This(x) = Both(x, zero) and That(x) = Both(zero, x), you've got even more homomorphism-trouble.

[runarorama]

@tailcalled The underlying list is accessible, but it has been normalized. The identities haven't been removed though. I notice that Data.Monoid.Coproduct has the same representation but provides no toList at all.

@davidk01 The book is much more geared to the FP beginner, although we try to provide lots of links to further material like this.

[robbieg8s]

Just a quick note - if i understand correctly, you are claiming that other examples of isomorphic monoids are (Int, +) and (Int, *), and (Boolean, &&) and (Boolean, ||). It certainly isn't the case that the monoids (Int, +) and (Int, *) are isomorphic. There are lots of ways to see this, but let's say f : Int => Int and g : Int => Int were a pair of mutually inverse monoid homomorphisms. That is, we have f(x+y) = f(x)*f(y), g(a*b) = g(a)+g(b), and g(f(x)) = x, f(g(a)) = a. Consider y = g(0) - that is, take 0 as an element of (Int, *), and use g to translate it to (Int, +). Then for any x in (Int, +), we have

x+y = g(f(x+y))=g(f(x)*f(y))=g(f(x)*f(g(0))=g(f(x)*0)=g(0)=y

It follows that x = 0 for every x in (Int, +), which is not so. In fact, (Int, +) is the free group on one generator. If you restrict to just non-negative integers under addition, you get the free monoid on one generator. By contrast, the positive integers under multiplication is the free monoid on infinitely many generators - the primes. Every integer is a product of primes, and they're never equal unless they have to be - that is, prime factorization is unique. You might be thinking of (Real, +) which is isomorphic to (PositiveReal, *) via exp and log. It is true that (Boolean, &&) and (Boolean, ||) are isomorphic as monoids via not : Boolean => Boolean and not : Boolean => Boolean - the monoid homomorphism properties are De Morgan's Laws, and not is its own inverse. In fact, this is true for Boolean algebras generally - any Boolean algebra has its join monoid inverse to its meet monoid via its not.

[runarorama]

@robbieg8s Awesome answer. Thanks for clearing that up.

[tomer-ben-david]

Perfect :)

[johnduffell]

I've only been learning functional programming for a month or two from your book, so forgive me if I'm wrong, but when doing the exercises I can't see why this wouldn't be a simple monoid on Either[A, B]?

def coproduct[A:Monoid,B:Monoid]: Monoid[Either[A, B]] =
  new Monoid[Either[A, B]] {
    def append(x: Either[A, B], y: Either[A, B]) = (x, y) match {
      case (Left(a1), Left(a2)) => Left(a1 |+| a2)
      case (Right(b1), Right(b2)) => Right(b1 |+| b2)
      case (Left(a), _) => Left(a)
      case (_, Left(a)) => Left(a)
    }
    val zero = Right(B.zero)
  }

It seems to conform to the laws, and having read your post, it seems close to your Eithers[A,B] only my version would actually discard all the Bs as soon as it saw an A, and just collapse all the As together not just consecutive ones. This could perhaps be useful for validation of a set of fields - if everything is Right you get the results stored in the rights, but if there are any errors (Lefts) then you just get a list of errors.

[tailcalled]

@johnduffell It is correct that what you have is a monoid, but it is not the coproduct monoid. The coproduct monoid has some nice properties that makes it behave more like Either, but among monoids.

[bblfish]

Great article! Because Monoids are such simple constructs this was really helpful to allow me to understand how category theory works. I discovered a couple of probably quite fundamental things that I had misunderstood reading this.

What is weird is that Monoid Products are so similar to Set products, but Monoid Sums/Coproducts are quite a lot more complex than Set Coproducts...

Btw. I found the Haskell Library Data.Monoid.Coproduct seems to be very similar, though I have not studied it in detail.

Just to help me think about Monoid Coproducts more I was wondering if there are good examples of when they come in useful. I have been playing with sums of Ints and Strings but was looking for a more revealing example.

Ah yes. I also found the code works nearly without change using cats rather than scalaz.

[robbieg8s]

What is weird is that Monoid Products are so similar to Set products, but Monoid Sums/Coproducts are quite a lot more complex than Set Coproducts...

There's a functor U : Monoids -> Sets which carries a monoid to it's underlying set. It's called the forgetful functor because it forgets the algebraic structure. There's a functor F : Sets -> Monoids which takes a set X to the free monoid with generators X, also known as List with 1 the empty list and concatenation for the operation. Now F and U are adjoint : for a set X and monoid M, monoid homorphisms FX -> M are isomorphic to functions X -> UM, natural in X and M.

It's a general fact that right adjoints like U preserve limits (such as products), so that U(M x N) =~ UM x UN - the underlying set of the monoid product is the set product of the underlying sets. Conversely, left adjoints like F preserve colimits (such as sums), so that F(X + Y) =~ FX + FY. This means that monoid + needs to be pretty complicated, because List<X+Y> is not simply described from List and List, because you need to let arbitrary interleavings happen.