Monoids, Bioids, and Beyond

Two View of Monoids.

Monoids

Monoids are defined in Haskell as follows:

class Monoid a where
    m_id :: a
    (++) :: a -> a -> a

Monoids define some operation with identity (here called m_id). We can define the required laws, identity, and associativity, as follows:

monoidLaw1, monoidLaw2 :: (Monoid a, Eq a) => a -> Bool
monoidLaw1 x = x ++ m_id == x
monoidLaw2 x = m_id ++ x == x

monoidLaw3 :: (Monoid a, Eq a) => a -> a -> a -> Bool
monoidLaw3 x y z = (x ++ y) ++ z == x ++ (y ++ z)

Morphisms

Now, I’ll introduce something else:

class (Morphism f) where
    id :: f x x
    (.) :: f b c -> f a b -> f a c

Morphisms also have laws:

morphismLaw1, morphismLaw2 :: (Morphism f, Eq (f a b)) => f a b -> Bool
morphismLaw1 f = f . id == f
morphismLaw2 f = id . f == f

morphismLaw3 :: (Morphism f, Eq (f a d)) => f c d -> f b c -> f a b -> Bool
morphismLaw3 f g h = (f . g) . h == f . (g . h)

This definition defines a morphism, or a generalization of a function, in the category of Haskell types.

We can make things instances of morphisms as such:

instance (Morphism (->)) where
    id x = x
    (f . g) x = f (g x)

Morphisms and Monoids

Note that while a Monoid is a concrete type, a Morphism is a higher-order-type that takes two types as inputs. However, apart from this, we have fairly similar set of given functions with a similar set of laws.

To make the comparison explicit, we can look at endomorphisms, that is morphisms from a set to itself.

data Endo morph set = Endo (morph set set)

instance (Morphism morph) => (Monoid (Endo morph set)) where
    m_id = Endo id
    Endo f ++ Endo g = Endo (f . g)

So, we can see that monoids can be viewed as morphisms from a set to itself. Here is a diagram of that. The elements of the monoid are the arrows.

In any case, we now have a new way of expressing a monoid: as a set of morphisms from a set to itself.

Bioids

We can define a bioid to be the arrows between two objects. These fall into four different sets, those from \(A \to A\), those from \(A \to B\), those from \(B \to A\), and those from \(B \to B\). This can be represented diagrammatically as follows:

If we want to enforce the laws of the category, we know that we need to enforce a monad structure on both \(A\) and \(B\). We also know that we must have four additional composition values. In Haskell syntax, we have:

class (Monoid aa, Monoid bb) => Bioid aa bb ab ba
        | aa -> ab, aa -> ba, bb -> ab, bb -> ba, ab -> aa, ab -> bb, ba -> aa, ba -> bb, aa -> bb, bb -> aa, ab -> ba, ba -> ab where
    id_a :: aa
    id_b :: bb
    (%%) :: ab -> ba -> aa
    (^^) :: ba -> ab -> bb

    (#>) :: ab -> aa -> ab
    (<#) :: aa -> ba -> ba
    ($>) :: bb -> ab -> ab
    (<$) :: ba -> bb -> ba

OK, I don’t want to write down the laws for that mess. I now understand why mathematicians stopped at monoids but not bioids. To be completely honest, I was hoping to get semirings out of this mess, but I don’t think it’s actually possible.

And Beyond

In any case, we can still notice something interesting about a Bioid. It has a total of eight composition rules, if you include the two monoid rules. How can we calculate this number in general?

First, let’s define an n-oid as the morphisms on a category with \(n\) objects. We know that there are \(n^2\) types of morphisms (\(n\) sources and \(n\) destinations). We also know that each composition rule contains three types in any order:

\(\circ :: m b c \to m a b \to m b c\)

So there are therefore \(n^3\) ++ equivalents on an n-oid. Yeah, in general that’s going to get messy very fast.