loading...

re: Explain what a monoid is Like I'm Five VIEW POST

FULL DISCUSSION
 

Monad or monoid?

The technical definition is a monoid is a semigroup with an identity. Which is not very ELI5.

So: a monoid is "a bunch of stuff, and a thing we do with that stuff, that behaves pretty intuitively." Which is vague as hell. But it's meant to be. Very frequently, things that behave like this "feel" like addition.

Like, say, shoving a bunch of piles of sticks together.

  1. If I have some sticks, and I shove them together, what's in the pile? Sticks, right? Yup.

  2. What if I shove them into smaller piles first and then sort of regroup those piles around themselves and then shove them together? Is it still a pile of sticks? What if I shove the sticks on the left first before I do the rest? Yup. Is it basically the same pile of sticks? Yup.

  3. If I have a bunch of sticks and shove No Sticks at it... did anything change? Nope.

The first two are what makes it a semigroup.

#1 is closure under a binary operation. Sure, there's lots of sticks, but I could split it into two groups, or add one stick at a time, or whatever. When I operate on the sticks using Shove to bring them together, I still have things that are sticks at the end. They didn't turn into frogs, I didn't carve them.

Fire would be not only non-binary, but also not closed -- if I use fire on the sticks, do I have sticks at the end? Well, no, not really. Burnt sticks, sure -- which noticeably, is sticks that have had the fire operation on them.

#2 is associativity. That means that the order we evaluate things in doesn't matter.

#3 is the identity. This is the thing that is analogous to zero -- if you take it, and apply your operation on it and something, nothing changes. So No Sticks would be it here.

From a programming perspective, strings concatenation is a good not-math example.

What's the binary operation? Concatenation. Joining things together. (Remember what I said about feeling like addition!) You operate only on two pieces at a time. If you had a million words, you'd still do it by adding one to another etc. a + b => ab

Is it closed under that operation? Closure means "I have stuff of this kind, do something to it, and still have that type at the end." So, if we take strings at stick them together, we have... a long string! So, yup, it's a string. Cool! So it's closed under our operation.

Is it associative? Yup! And remember, this doesn't mean that the order doesn't matter--but that the order of evaluation doesn't matter. he + llo gives the same result as h + ello or h + el + lo or h + (el + lo) or (h + el) + lo or ((h + (e + l) + l) + o are all hello at the end. (Note that 'order does matter' here would be -- is he + llo the same as lh + elo? Nope, hello is not lhelo.

Is there an identity for this operation? Yup -- the empty string. apple + "" is apple. Still a string. "" is a string, too, just one without anything in it. So we can use it for our operation, still get a string -- the same string we started with, in fact!

 

Now that I know the difference. I know that my picture below is wrong.

Free Monoid!

Code of Conduct Report abuse