Thursday 12 November 2015

Monads, who's afraid of Monads (and C++)?


Nowadays every programmer has heard of Monads, and either has a PhD in CS or is afraid of them (or both...). When I first heard of it (my university years are quite distant, and the category theory wasn't en vogue yet in that distant time) I though: "Monadology? Leibniz? WTF? Didn't Kant disprove that?"

Because writing a monad tutorial is sooo last decade, I will just reference one quite good, practical introduction to that stuff that is using Javascript (Javascript! => nice, no need to learn a new, unreadable & incomprehensible language first! 😀). I think it's <praise> practical enough to be useful, but then again not shirking back from maths in order to please the reader</praise>.

If you don't want to read it, and are smug enough to think that a 10.000 feet view is all you'll ever need, voila - there's a short summary:

Monads Summary

1. Functor

An object encapsulating a value, plus an interface (called "fmap" for historical reasons) taking some function to act on that value. Because of the immutability/pure functions stuff it doesn't change the contained value, of course, but produces a new functor instance.
            +------------+                                  +------------+
            |   value    |                                  |  newvalue  |
      f     |            |     fmap()                       |            |
  +-------> |   fmap()   |  +--------->  f(value) +-------> |   fmap()   |
            |            |                                  |            |
            +------------+                                  +------------+
Is the picture clear enough? OK, let's continue.

2. Monad

Is a Functor which has a "collapse" and "wrap" methods. Collapse (also called "join" in some contexts) will remove one level of the packaging added by the functor, "wrap" (also called "return") will remove it. Simple like that!
  +-------------------------------+                               
  |                               |                               
  |            +-------------+    |                 +------------+
  |            |             |    |       join      |            |
  |   value =  |    value    |    |   +---------->  |   value    |
  |            |             |    |                 |            |
  |            +-------------+    |                 +------------+
  |                               |                               
  +-------------------------------+                               

                         +------------+
               wrap      |            |
   value   +---------->  |   value    |
                         |            |
                         +------------+
Well not quite, the classic usage case** that made the whole concept famous, hinges on another method called "mbind" which allows us to apply several functions to the monadic value in a row, an emulation of imperative programming (imperative always means in this context "evil, evil") standard sequential flow of control. But wait a minute: isn't that simply "fmap" + "join"? Yeah, you guessed it, it is***.

Simple? Yes, I think so. Was it that complicated? No. So why all that fuss? Don't know, won't comment here, make your own mind.

But why should this be useful? Again, I don't want to write a monad tutorial here (it's so ...), read the Javascript  book, or maybe some general functional programming resources. Start with error handling and the Maybe type.

High level enough? If not, take on with this classic explanation: "Monad is just a monoid in category of endofunctors, what's the problem?"*. Here you'll need some category theory/maths, there's no mercy:

Another Summary

1. Endofunctor

A functor (see above) mapping values to values of the same type. On that level, functor is a mapping between categories, where a category is a set of values plus all the functions between the values. Thus our functor above maps values of type A to values of type B and functions A->A to functions B->B, respecting some common sense restrictions on its way.

You see, it's getting pretty messy quite quickly, but take it as a mathematical recreation and follow through.

2. Category of endofunctors

All endofunctors plus functions mapping one endofuctor (i.e. a functor, i.e a mapping from one "set" of object+mappings to another) to another.

3. Monoid in that category...

Monoid is a "set" of objects having a function A->A defined for them (usually called "m-append", you get it, basically a glorified string or array) plus a neutral element. Now just imagine that for the category of endofunctors, do some math, an you will see that all that gunk collapses to our old, trusty monad as described above.

Why so complicated? Well, that's maths (and mathematicians) for you. But don't despair, it's only a construction of a human mind, so everyone can get a grip of it. The question is only if that does feel like fun for you or not. In all cases, don't mythologize!

And That's It!

Now if you feel like that, you can try out this things in C++, there are a couple libraries implementing this stuff like thisthis or that. Simple, self-sufficient implementation is possible too! There was even a C++ language proposal for a monadic expected class to be used for error handling, so somehow this stuff is coming. Now as you are not intimidated anymore, go and try it!

But first read the Javascript online book to familiarize yourself with the concepts. And yes, you don't need to learn Haskell**** and then read Haskell books for that! So do not fear.

Maybe you'd even like to go further and investigate monadic parsers (because I like F# you'll get this link and this link), applicatives & applicative parsers (sorry no link here, didn't find anything which is simple enough) or free monads. Who knows, the sky is the limit now, an you do not fear anything! At least you can read the jargon without cold shivers running down your spine.

PS: Maths guys, please no hair-splitting, I didn't cross-checked it with MacLane & Avodey, just wrote it down as I remembered it. However notice the "set" usage ;) ...


Update: If you want to continue in a similar vein, that's an interesting page demythologizing func. prog. on its own: github.hemanth.functional-programming-jargon!

--
* famously attributed to Phillip Wadler, but it's rather a joke, as the real sentence was:
"All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor."
** by..., you guessed it, Phil Wadler: "Monads for functional programming" (it's CS + FP but nonetheless quite readable, you may risk a try now when you fear nothing!)

*** in some contexts "point" and "flatMap" are used, the first for "wrap", the second for "fmap" + "collapse"

**** "I'm Haskell, the language of purebloods..." 😉

No comments: