HasPlained: Monoids
Just happened upon these illuminative insights for "Developing an intuition for Monoid" — here are the essentials, distilled and/or paraphrased-for-clarity.
Just a fancy moniker for any sets of values with both:
- a closed binary operation
x <> y
(or mappend) that is associative ie.(x <> (y <> z)) == ((x <> y) <> z)
, - and an identity value
id
(or mempty, or call it nil / default / unit if you will.. you get the idea) such that(x <> id) == (id <> x) == x
Examples
- numbers: for all values,
(n + 0) == n
- so
id = 0
with(<>) = (+)
is a monoid for numbers
- so
- numbers: for all values,
(n × 1) == n
- so
id = 1
with(<>) = (×)
is a monoid for numbers
- so
- booleans: for all values,
(b || False) == b
- so
id = False
with(<>) = (||)
is a monoid for booleans
- so
- booleans: for all values,
(b && True) == b
- so
id = True
with(<>) = (&&)
is a monoid for booleans
- so
- lists / strings: for all strings,
(s ++ "") == s
; for all lists,(l ++ []) == l
- so
id = []
/id = ""
with(<>) = (++)
is a monoid for lists/strings
- so
Distiller from [X] to X
So intuitively, if there's an obvious (associative) combining function <>
from both [X]-to-X and []-to-Xdefault/empty (where also X == (X <> Xdefault/empty)
, always) — then that <> with that Xdefault/empty make a monoid for all X.
- ie. when asking for a way to combine [X] to X, this also needs to give an answer for the empty list [], which implies there's a default value you can assign to the empty list: this is the difference between a monoid and a semigroup.
- more: on
()
, why booleans/numbers can be seen as monoids but aren'tMonoid
instances by default, etc..
Foldable / containers
Given a Data.Foldable
instance for some container (list, map, etc..), you can write a generic fold
function that only takes one argument (the container).
- If you have a value of a type
f a
(withf
an instance ofFoldable
anda
an instance ofMonoid
), then instead offoldr someFunc startVal container
you can just write:fold container
. - The
Foldable
part is what's important for the container.Monoid
has no concept of a "container" whatsoever, it simply provides a "zero" value and a way to combine two values together. - I want to emphasize that it's the operator that matters, not the type — more..
So at the end of the day, this all just means that monoids serve as the language used by folds to tear down bigger structures. What exactly that language expresses is up to the Monoid
, and what it means to be torn down is up to the instance of Foldable
.
Remarks
Grasping all of the above, we can now parse Diehl: "A monoid is a combination of a unit and a single associative operation over a set of values." So far, I haven't encountered (neither before nor upon having absorbed the above findings) any pressing need of defining and wiring up custom Monoid
instances for explicit use with any Foldable
s (or any other purpose), but it'll probably come up some obscure way when least expected.