Normally I put the question before the context, but in this case I want to admit the possibility that the context and my understanding nullify the question. Plus it helps me think through my question.
I recently started reading Category Theory for Programmers (Bartosz Milewski), and this is my understanding of categories: they are "algebraic structures" which consist of objects and arrows/morphisms between those objects. The morphisms have to obey the laws of associativity, so
$$ a \rightarrow ( b \rightarrow c ) = ( a \rightarrow b ) \rightarrow c $$
And there must be an identity morphism for each object.
Now, Milewski goes on to explain that monoids (which I'm pretty comfortable with in the set-theoretic sense) are also viewable as categories. This is the part I am having trouble with. One of the exercises in the book is to consider the Boolean-and monoid (booleans with the and operator) as a category:
Represent the Bool monoid with the AND operator as a category: List the morphisms and their rules of composition.
I want to give some examples, which I'll do in a SML (though I'll borrow Haskell names).
The monoid could be described set-theoretically with the following signature:
signature MONOID = sig type m val mempty : m val mappend : m -> m -> m end
Further, the monoid for booleans with the and operator would be given as
structure BoolAnd : MONOID = struct type m = bool val mempty = true fun mappend x y = x andalso y end
So, here is my understanding of this monoid as a category and its morphisms: is it correct?
- The objects in the category are booleans (true and false) and functions from booleans to booleans
BoolAnd.mappendis a morphism from the former to the latter
mappend trueis an identity morphism for the function objects in the category (I say "an" because isn't the actual identity function
fun id x = xalso an identity morphism for the functions, thanks to polymorphic types? Or does that not count in category-land? I know that
mappend trueis equivalent to the identity function under composition of functions with type
bool -> bool.)
- the identity morphism for boolean objects appears to be just
fun id (b:bool) = b
- the given identity morphisms should be associative:
(* example, not proof *) - open BoolAnd; - (id o (mappend true)) o not; val it = fn : bool -> bool - it false; val it = true - id o ((mappend true) o not); val it = fn : bool -> bool - it false; val it = true
The rules of composition seem to be that
mappend true is the identity, while
mappend false is a "sink" of sorts, causing the resulting function to always
return false. But
mappend don't directly compose, because the types
do not align (when
id is specialized to booleans, as in the bullets above).
Am I missing something? Is something wrong? Did I give too much detail (there seems to be an emphasis on avoiding digging in to the objects too much)?
I ask this both to confirm my understanding so that I have a good foundation for the remainder of the book and also because it took me a long time to identify the objects and morphisms at work; some of them I am still shaky about.