Phil Schumann, Germany
 Software Developer

27 Dec 2016 Just happened upon these illuminative insights for "Developing an intuition for Monoid" — here are the essentials, distilled and/or paraphrased-for-clarity.

HasPlained: Monoids

The HasPlained series collects "unusually-intuitive, remarkably-plain" (for this field) explanations on the more abstract Functional Programming / Haskell concepts.

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
  • numbers: for all values, (n × 1) == n
    — so id = 1 with (<>) = (×) is a monoid for numbers
  • booleans: for all values, (b || False) == b
    — so id = False with (<>) = (||) is a monoid for booleans
  • booleans: for all values, (b && True) == b
    — so id = True with (<>) = (&&) is a monoid for booleans
  • lists / strings: for all strings, (s ++ "") == s; for all lists, (l ++ []) == l
    — so id = [] / id = "" with (<>) = (++) is a monoid for lists/strings

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't Monoid 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 (with f an instance of Foldable and a an instance of Monoid), then instead of foldr 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 typemore..

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 Foldables (or any other purpose), but it'll probably come up some obscure way when least expected.

 
Cogent
The chief source of problems is "solutions".
Eric Sevareid
Sourcery
Working with since1998 » BasicPascal1999 » HTMLASP2000 » SQLCSSJSVB2001 » JavaPHP2002 » C#ASP.NET2003 » XSLT / XPath2004 » Prolog2006 » SharePoint2008 » F# • Python • Lisp2011 » Go • WebGL • Node.js • CoffeeScript • 2012 » OpenGLGLSL2015 » Haskell2016 » TypeScriptElm2017 » PureScriptVue.jsGraphQL2018 » Lua
Details..
Making-of
Site theme: none; hand-crafted.
Static site gen: HaXtatic.
Icons, logos, fonts: © respective owners.