8
$\begingroup$

I don't have a strong math background (engineering math) so I am at a bit of a disadvantage here but I have been trying to learn the broad strokes of Category Theory to help get a fuller picture of some of the Functional programming languages I use (Haskell, Scala, F#, etc.).

I am reading 'An Introduction to Category Theory' by Harold Simmons and ran into something in the first chapter regarding Monoids that leaves me a bit confused.

He states that a Monoid is a structure $(R, *, 1)$ where $R$ is a set, $*$ is a binary operation on $R$ and $1$ is an element of $R$ that functions as an identity element. So far, so good.

He goes on to state that a monoid morphism between two monoids:

$$p: R \to S$$

is a function that respects the structure of the monoids. He then explains that this means:

$$p(r*s) = p(r) * p(s),\quad\mathrm{and}\quad p(1) = 1$$

where $r$ and $s$ are elements of $R$.

The question I have is that this seems to make certain assumptions: specifically, that $R$ and $S$ are the same monoid. I say this since $p(r)$ is a morphism from $R$ to $S$ and $*$ is defined for $R$, but not necessarily for $S$.

Have I missed something here?

$\endgroup$
  • 2
    $\begingroup$ I find it a bit ironic that you are a Haskell user... notice how the author is simply using overloading (i.e. he uses $1$ for both $1_R$ and $1_S$ etc.) plus type inference to determine which overload to choose... exactly how Haskell does this stuff (think of the literal 1 that can be both 1 :: Int and 1 :: Float or something else, but if the compiler can infer the type you don't have to specify it). In Haskell you'd still write that p is a monoid morphism if it satisfies: p (mappend r s) == mappend (p r) (p s). $\endgroup$ – Bakuriu Jul 4 '15 at 12:39
  • $\begingroup$ Yeah, I see that now. I wasn't thinking like a compiler. $\endgroup$ – melston Jul 5 '15 at 16:00
23
$\begingroup$

A more detailed way to write the statment (i.e. without abuse of notation) would be the following:

Let $(R,*_R,1_R)$ and $(S,*_S,1_S)$ be two monoids, then a function $p:R\to S$ is called a monoid morphism if for any $r_1,r_2\in R$ $$p(r_1*_Rr_2) = p(r_1)*_Sp(r_2)$$ and $$p(1_R) = 1_S.$$

However, in most sources the subscript indicating the monoid we're in is left away to ease notation, as it is assumed that the reader can easily deduce it. You'll get used to it, don't worry.

| cite | improve this answer | |
$\endgroup$
15
$\begingroup$

This is what a mathematician might call abuse of notation and what a computer scientist might call overloading: the * symbol is being used to denote the monoid operation in both $R$ and $S$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ That was what I suspected but didn't think I could just assume it was so. So, apparently, the identity element is the same in both monoids as well? $\endgroup$ – melston Jul 3 '15 at 18:11
  • 1
    $\begingroup$ @melston: no, that's just another abuse of notation. $\endgroup$ – Qiaochu Yuan Jul 3 '15 at 18:12
  • 1
    $\begingroup$ So maybe I don't understand after all. The * symbol represents <the> monoid operation in both R and S? Or does it represent the monoid operation in R and (a possibly different) monoid operation in S? $\endgroup$ – melston Jul 3 '15 at 18:16
  • 4
    $\begingroup$ @melston: the latter. $\endgroup$ – Qiaochu Yuan Jul 3 '15 at 18:26
4
$\begingroup$

Why not write this out in Haskell! The monoid type class is defined as

class Monoid m where
  mempty :: m          -- Simmons calls this `1`
  (<>) :: m -> m -> m  -- aka `*`. (Or `mappend`.)

If now the types R and S are monoids, i.e.

instance Monoid R where { ... }
instance Monoid S where { ... }

then a function p :: R -> S is a monoid morphism if p (a<>b) ≡ p a <> p b, and p mempty ≡ mempty. Or, with explicit type annotations,

p (a<>b :: R) :: S
    ≡ (p a :: S) <> (p b :: S)
p (mempty :: R) ≡ (mempty :: S)

Note that the instantiations of <> and mempty belong to different instances of the monoid methods: on the LHS, it's the Monoid R instance, on the RHS it's the Monoid S instance. (Haskell's HM type system infers this by itself, if you don't write out the type signatures explicitly.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I believe it would be clearer if you also point out that the Haskell compiler is able to automatically infer the types of the instantiations, since this is what was expected by the author of the book from the reader. $\endgroup$ – Bakuriu Jul 4 '15 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.