Beyond “Monads and Gonads”

Gist: There’s this famous “Monads and Gonads” video from Doug Crockford. To me it is cryptic, kind of elitist: it flies over a lot of fairly complex stuff without giving sound grip on the matter. I can’t imagine anyone ‘seeing’ monads for the first time thanks to this presentation.
The major merits of this video are to state clearly that monads don’t need a type system, that monads ought to be objects taking care of their own adherence to monad laws and to show that JS is perfectly suited to manage those objects using a terse, straightforward syntax. I also liked the idea of using a MONAD “macroid”(that’s a JS function that mimics a Scheme macro) to produce the various kinds of monads from a single archetype.
Besides, imho the presentation cuts too many corners and stops short of presenting and explaining some meaningful example. This led me to fork the original Crockford’s code and produce further applications of the monads presented inside it as well as of new types.

During the preparation of this material I have received great benefit from discovering and consulting Monads by Mistake.

The macroid and its modifier

The base of the whole story is this JS snippet:


function MONAD(modifier) {
  var prototype = Object.create(null);
  function unit(value) {
    var monad = Object.create(prototype);
    monad.bind = function (func, args) {
      return func.apply(
        undefined,
        [value].concat(Array.prototype.slice.apply(args || []))
      );
    };
    if (typeof modifier === 'function') {
      value = modifier(monad, value);
    }
    return monad;
  }
  // a few features more, omitted now....
  return unit;
}

For the complete commented code, please refer to the original file monad.js.

Douglas Crockford calls this a macroid, and correctly so. It is a blueprint for building monad constructors, and in Scheme it would be implemented using a macro. In JS there’s no need for special constructs; syntax is homogeneous and everything flies like a breeze.

A straight run of MONAD with no args produces a constructor for instances of the clueless identity monad.

The bind function covers a minimal but reliable role, applying the monad value to the bound function and returning whatever result. If we care to write fluent, chained code it’s up to the bound function to make sure that the result is a monad, as there’s no type system to save the day.

All the examples from here on are to be found in the forked repository on my GitHub account.

var identity = MONAD(); // no args
var id = identity('Hello, I\'m an identity\n Try to stop me from alerting you...');
id.bind(alert); // no way to stop it...

The modifier is a function given as argument to the macroid. It’s closed over and invoked afterwards, during the run of unit. Its basic role is to modify the value being passed to unit:


value = modifier(monad, value);

But there’s no limit to what the modifier can do. For example, it can redefine the monad.bind function for every instance being constructed.

Tuning the modifier allows to instantiate different monads, provided its run doesn’t screw up the behavior of the final product with respect to the monad laws. Crockford shows a custom modifier for Maybe, I present here one for State and one for Writer; there’s gotta be a modifier for each custom monad we may care to invent.

The MONAD macroid provides also a few facilities to augment the prototype of the monad being defined:

  • a method method, that attaches monadic functions
  • a lift method that lifts and attaches plain functions
  • lift_value (remarkably confusing name), a method that binds any function to the monad and returns whatever the function produces

The talk provides very few examples of usage and not all these facilities of the macroid are put at work. In the rest of this post that will be done.

Bind on steroids

An interesting feature shown by Crockford is the possibility for bind to handle additional parameters on top of the traditional single value passed by the current monad to the bound function.

A typical bindable function is unary and has type

famb :: a -> monad b

so that we can take a ma :: monad a and do:

ma.bind(famb) :: monad b

Crockford passes to bind any function and, when the function is not unary, expects you to provide an additional array of arguments. Those arguments are passed to the bound function immediately after the canonic value coming from the current monad. This allows to join any number of factors into the run of our monad, possibly other monad chains. Gotta think some more about this.

These monads are all JS objects so we can happily use the name bind without overriding anything (conversely to what I do in my own state monad function).

The mysterious Ajax monad

The “ajax monad” in the video got me thinking. I had never thought of chained function calls as full-fledged monads. Monads are more than merely return this; at the end of each function body.

Nevertheless, Crockford shows what apparently is a plain chain of calls and says happily “we’ve been doing monads all the time!”. I’d disagree with that. My clumsy “fluent” interfaces, jam-packed with workarounds to preserve chainability in all known situations, and ready to blast at the next new legitimate combination attempted by any user, were miles away from the reliable robustness of monad chains.

If you google “ajax monad” all you get is pointers to Doug’s video and to its commentators (looking forward to see this post ranked high on the search results page 😉 ), so what the hell is this “ajax monad”? I have a theory:

There’s no ajax monad because the ajax monad is an identity monad created on the fly and equipped with the methods you need for today’s job. Those methods must be bindable, or the chain will break. Let’s prepare an ajax monad:

/* my own ajax implementation has also one method to concat strings
* and one method to extract the value and end the chain */
var ajax = MONAD()
  .lift('alert', alert)
  .lift('smarterAlert', function(v) {
    alert(v);
    return v;
  });
// monad.concat('whatever') will be a monad
var concat1 = MONAD()
  .lift('concat', function (v,b) {
    return v.concat(b); // Doug's bind allows further args
  })
  // monad.value() will be a plain value
  .lift_value('value', function (s) {
    return s; // end the chain.
  }); 

Lifting alert, which is unary, is no big deal: the monad will feed its own value to the popup. Lifting that anonymous binary lambda is interesting, because it saves one stack level. Otherwise it ought to be made this way:

var concat2 = function(b) {
  return function(v) {
    return ajax(v.concat(b));
  }
};

and get chained through:


monad.bind(concat2('whatever'));

Let’s start the monad:


var start = ajax('-->');

make it flow:

var firstSteps = start
  .concat('A')
  .concat('B')
  .concat('C')
  .bind(concat2('filippo'));

keep going, and imagine all sorts of blocking AJAX calls patiently awaited for inside the original macroid closures:

var otherSteps = firstSteps
  .bind(function (a,b) { // another binary function
    return ajax(a.length + 'EEE' + b)
  },['_Z_'])
  .concat('f');

Fetch the value and splash it to the screen…


alert(firstSteps.value()); // '-->ABCfilippo'

…or let the monad take care of that:

otherSteps.smarterAlert() // '13EEE_Z_f'
  .concat('STOP!').alert(); // '13EEE_Z_fSTOP!'

Since window.alert returns undefined, invoking monad.alert returns ajax(undefined); this way you’re free to start chaining all over again.

Thinking twice about what I said before, actually I see an “ajax monad” around: that’s the _.chain(array)........value(); construct in underscore.js. I’m afraid ajax monads are indistinguishable from whatever botched “fluent interface”.

Crockford’s Maybe (modifier in action!!)

The modifier for the Maybe intercepts the value and, if it’s null||undefined, it makes the current monad instance a numb Nothing by making sure that from now on the bind function will return the current monad instance regardless of the function being bound to it.

Let’s just take the original implementation, which encloses a lifted alert function, and play with it a bit.

We may invent a constructor for bindable functions:

var fVamb = function (V) {
  return function (a) {
    return maybe(a + V);
  }
}

…a bindable showstopper:

var chainBreaker = function(a) {
  return maybe(undefined); // that's a Nothing
}

…and then put things at work

var nothing = maybe(null);

nothing
 .bind(fVamb('xxx')) // no crash
 .alert(); // no popup

var some = maybe('some');

some
 .bind(fVamb('X'))
 .bind(fVamb('YZ'))
 .alert(); // 'someXYZ'

some
 .bind(fVamb('X'))
 .bind(chainBreaker) // ouch!
 .alert(); // no popup

Muzietto’s State

Things start to become interesting with the implementation of the state monad. The modifier for State is obviously longer and shows the power of the macroid idea. The value we pass to unit is a s -> [s,a] function, so the modifier is:

function (monad, stateFun) {
  // NB: monad :: Object, stateFun :: s -> [s,a]
  monad.bind = function (fasb) { // fasb :: a -> state b
    return state(function(s) {
      var scp = monad.run(s),
      nextState = scp[0],
      nextValue = scp[1];
      return func.apply(
        undefined,
        [nextValue].concat(Array.prototype.slice.apply(args || []))
      ).run(nextState);
      });
  };
  monad.run = function(s) {
    return stateFun(s);
  };
  return stateFun;
}

It is necessary to pass a run method to the monad in order to invoke the stateFun function at the heart of the monad, alike Haskell’s runState. Crockford’s implementation assumes that monad instances must be full-fledged JS objects. State monads are actually functions (and so is my own implementation of state); I have played a bit with the macroid, trying to differentiate its final products, but the code is based on Object.create() and I decided it should better remain like that.

This minimalistic implementation of State requires in any case two bindable functions to set and get the current state during the monad run; they are implemented as “static methods” for the monad:

state.setState = function (newState) {
  return state(function () {
    return [newState, undefined];
  });
};

state.getState = function () {
 return state(function (s) {
 return [s, s];
 });
 };

This macroid-based implementation handles all the use cases I’ve dealt with so far.

Talking about the state monad run that prompts the user for a name and then gives greetings, it is interesting to see here a case in which we bind binary functions during the macroid run, and then provide the second parameters during the monad run. This is alike the creation “on the fly” of the ajax monad earlier in this post, and allows to see once more the fluent interface at work:

// getText and alertText have been added to the monad through lift
var askThenGreet = start
  .getText('what is your name?')
  .alertText('welcome');

askThenGreet.run('whatever'); // start the monad run

promptThenGreet

As original contribution, after the tree labeler here goes a very simple list labeler:

/*
* listLabeler list =
*   list match
*     | [] -> return (s -> (s,[]))
*     | x:xs -> do
*           n <- getState()
*           _ <- setState(n+1)
*           bb <- listLabeler xs
*           return $ [n,x]:bb
*/
var listLabeler = function (list) {
  if (list.length === 0) {
    return state(function (s) {
      return [s, []];
    });
  } else {
    var x = list.shift();
    return state.getState()
      .bind(function (n) {
        return state.setState(n + 1)
          .bind(function (_) {
            return listLabeler(list)
              .bind(function (bb) {
                return state(function (s) {
                  return [s, [[n, x]].concat(bb)];
                });
              });
          });
      });
  }
};

list_labeler

In the code of the state monad I present also a mixed monad named SE (State+Error), along with a little application as list labeler. The bizantine complexity of the resulting code should be valid evidence of the disadvantages arising when one tries to mix monads together, and suggest to try monad transformers instead.

The Writer

Here I’ve just prepared the field, because next time I need a writer (I use them mostly for form validation but next time is probably going be a flow control mechanism) I could use the macroid to provide the monad of all various functor, applicative and monoid features in an orderly fashion.

Here goes the modifier:

function(monad, couple) {
// NB: monad :: Object, couple :: [value, monoid]
// default monoid is string
  if (!Array.isArray(couple)) {
    couple = [couple, ''];
  }
  var value = couple[0];
  var monoid = couple[1];
  // define a mappend function tailored to the given monoid
  var mappend = function(monoid) {
    switch (typeof monoid) {
      case 'number':
      case 'string':
        return function(value) { return monoid + value; }
        break;
      case 'boolean': // use case for booleans is form validation
        return function(value) { return monoid && value; }
        break;
      case 'object':
        if (Array.isArray(monoid)) { // case 'array'
          return function(value) { return monoid.concat(value); }
          break;
        }
      case 'function': // all untested
      case 'Sum':
      case 'Prod':
      case 'Any':
      case 'All':
      case 'Ord':
        return function(value) { return monoid.mappend(value); }
    }
  }(monoid);
  monad.bind = function(fawb) { // fawb :: a -> writer b
    var newCouple = fawb(value).run();
    return writer([newCouple[0], mappend(newCouple[1])]);
  }
  monad.run = function() {
    return couple;
  }
  monad._1 = function() {
    return couple[0];
  }();
  monad._2 = function() {
    return couple[1];
  }();
  return couple;
}

Same as in the case of State, we must provide methods in order to extract value from the monad. I appreciate my own implementation of Writer (still undocumented on this blog) which is based upon a real 2-elements JS array and that returns values just by invoking monad[0] or monad[1]. In this case I decided to provide a run method (a.k.a. runWriter in Haskell) and two Scala-like getters _1 and _2.

Here’s an example of macroid-based writer using a list as accumulator:

var start = writer([0,[]]);
var carryOn = function(x) {
  return writer([x+1,[x]]);
}

var enumerationOfFive = start
  .bind(carryOn)
  .bind(carryOn)
  .bind(carryOn)
  .bind(carryOn)
  .bind(carryOn);

alert(enumerationOfFive.run()); // [5,[1,2,3,4]]
alert(enumerationOfFive._1); // 5
alert(enumerationOfFive._2); // [1,2,3,4]

This writer monad is ready to accept a wide range of monoids, most of which are so far just mentioned in the mappend function. They are anyhow supposed to take the same role as they do in Haskell.

As mentioned before, all the examples presented in this page are to be found in the forked repository on my GitHub account.

Promises as Vows

The second part of the video introduces very briefly the second script in the original GitHub repository.

Promises are implemented under the name of vows. Code looks robust and elegant, as it’s usual from Crockford. It looks like it could be possible to achieve support for deferreds with 3 kB of code.

A future post will comment that code and put it into action.

Advertisements

One thought on “Beyond “Monads and Gonads”

  1. Dmitri Lebedev says:

    Ottimo lavoro, avevo visto la lezione del Crockford e volevo usare i suoi strumenti, ma il repositorio aveva poca materia, si dovrebbe scrivere molto da se. In fatti hai elaborato le soluzioni di molte di quelle domande su StackOverflow, tipo come creare un callback che si avvia dopo di tutti gli eventi, o al primo evento. Tuo repo deve essere una soluzione tipica per queste domande. Grazie mille!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s