State monad goes to JS town (and starts swinging…)

Gist: JavaScript is the only language I am aware of that allows to invoke a monadic function, like state is, simply by calling an instance by its name and sticking a parameter between two round brackets: myStateMonad(aState) will return a state-content pair that I chose to represent as {state:aState,value:aValue}, but that could as well piggyback on arrays and read like [aState,aValue].

And because you have a monad instance equipped with all the required monad stuff, you may simply bind it to a custom-built function, and you get another monad instance. Then, keep chaining…

This is what I call intuitive. These concepts read easier in JS than in most other languages.

Too bad JavaScript doesn’t have do-notation: that would end whatever discussion about the best language for learning FP 🙂

Recap: a chainable state monad in JavaScript

In a previous post I have described a chainable state monad. The major points of the implementation are:

  • a static monad data constructor that decorates a JS function s -> (s,a) with methods that make it a real monad instance, notably bind(*)
  • a static unit constructor that wraps a value inside a state monad
  • an instance method bind that allows to chain the current instance state a to a function with type a -> state b
  • a few other methods for flow control and error handling

(*) alas, the work of the monad constructor causes an override of Function.prototype.bind; this suggests to give bind another name in any production-level implementation of these concepts (what about flatMap?)

In that post I’ve used my state monad as a mere I/O monad to handle user interaction: in all those examples the state of the calculation (a human was asked to input stepwise his/her first and then family names) was kept inside a single closure and no use was made of the capabilities of the monad to receive a state, modify it and pass it further.

I present here a few cases, progressively complex, where the state gets modified in the process. All these cases are to be found in the geiesmonads GitHub repository.

Build a key-value-pair dictionary, and use it

In the above mentioned post, the function getString uses a JS prompt to capture some user input:

var getString = function(msg) {
  return Monad.state.unit(prompt(msg));
};

We can modify it to enrich the state. Assuming the state is a JS object we can ask the user a key-value pair in the form of a string containing an underscore to separate the key from the value. And then stick the pair in the object. Please refer to the geiesmonads_2.0Tests.js file.


var putKVPInState = function(msg) { // KeyValuePair
  // invoke the monad constructor with a valid s -> (s,a)
  return Monad.state.monad(function(state) {
    var keyValue = prompt(msg).split('_');
    state[keyValue[0]] = keyValue[1]; // enrich state
    // value may come handy in the closure...
    return {value:keyValue[1],state:state};
  });
}

The dual of this function is a state monad that reads the JS object and prints data from it.


var getValuesFromState = function(msg) {
  return Monad.state.monad(function(state) {
    // we assume state = {x:XVAL,y:YVAL}
    var undy = alert(msg + ' ' + state.x + ' ' + state.y);
    return {value:undy,state:state};
  });
}

It would be nice to put all this at work through a for-comp:


for {
  _ <- putKVPInState('gimme x_YOURFIRSTNAME')
  _ <- putKVPInState('gimme y_YOURFAMILYNAME')
} yield getValuesFromState('state is telling me you are ')

but JS is more verbose:

var chain = nullState()
  .bind(function(_) {
    return putKVPInState('gimme x_YOURFIRSTNAME'); })
  .bind(function(_) {
    return putKVPInState('gimme y_YOURFAMILYNAME'); })
  .bind(function(_) {
    return getValuesFromState('state is telling me you are '); });

kvp_in_state

The point here is that the closure is not used to pass data to getValuesFromState. This is neat, because it takes away the need to wrap the various calls to bind with onion-like brackets.

Traversing a binary tree

One famous monad-related source is the exercise prepared in 2008 for Microsoft developers by Brian Beckman, one of the creators of LINQ, and published by Channel 9.

This exercise, originally written in C#, involves the traversal of a binary tree, first using a traditional recursive loop and then building and running a state monad.

I have already ported the exercise to Java 8 and presented there the ins & outs of the monadic traversal procedure. The JS porting of the exercise is also present in release 2.0 of geiesmonads.

The string-labeled tree on the left is transformed into a tree of state-content pairs. The state bit is an increasing integer, while the content is the original label.
The string-labeled tree on the left is transformed into a tree of state-content pairs. The state bit is an increasing integer counter, while the content is the original label. The example at [1] is truly precious, as it shows two different ways to perform the modification of the tree:
1) in the first way (non monadic) one is forced to explicitly pass the int counter as parameter through the recursive calls of the tree-traversing function. See ManualLabeling.java
2) afterwards [1] shows how the monadic tree-traversing function passes recursively the sole branches and leaves of the tree, as the evolving state remains embedded and transparent inside the monad containers. See MonadicLabeling.java

The function monadicLabeler(tree) checks whether tree is a leaf or a branch and returns accordingly different values: leafSM or branchSM. Processing a branch(left,right) involves (not surprisingly) two recursive calls.

I found it interesting to compare some Java 8 expressions with their JS counterparts:

The state updater

When we meet a leaf, state must be used to label it, at the same time it gotta be increased by one and passed down the chain. Managing the state is the job for a state monad with type s -> (s,s). It is a close relative of what they call getState or just get, but while get simply copies che current state into the value slot here the state is modified in the process. The run of this updateState monad produces a pair {state:updatedState,value:state}.

Java version:

StateMonad updateState = new StateMonad(
  n -> new Scp(n + 1, n)); // Scp = state-content pair

Javascript version:

updateState = Monad.state.monad(function(n){
  return {state:n+1,value:n};
});

In a comparison of the clarity of intent, I’d say this is a Java/JS tie.

Creating a pair-labeled leaf

Here Javascript takes off…

The state-handling monad from the previous paragraph is meant to be bound to a function that takes the current state as a value and produces a new state monad that uses the value received to build the pair-labeled leaf, whilst passing implicitly whatever state it receives (that’s the updated state) down the chain.

The idea is to take a leaf(string) and return a leaf(n,string), where n is the value provided by updateState (in other words, the current state). All this must be merged in the flow of the monad.

Java version:

StateMonad<Integer, Tr<Scp>> leafSM =
updateState.bind((Integer state) -> new StateMonad<Integer, Tr<Scp>>(
  (Integer s) -> new Scp<Integer, Tr<Scp>>
    (s,new Lf<Scp>
      (new Scp(state,leaf.contents)))));

Javascript version:

leafSM = updateState.bind(function(n) {
  return Monad.state.monad(function(s) {
    return {state:s,value:leaf([n,tree()])};
  });
});

Following the JS version is like reading plain English prose. Any function bindable to a monad a must be of type a -> monad b; in the case of updateState the type is int -> state leaf([int,string]). The state monad we have to return is based upon a lambda that we build explicitly and pass to the constructor. Once provided with a state, that function will produce the leaf we desire.

In alternative to the constructor call, we may simply return unit(leaf([n,tree()])).

Handling the branches

In this case the Java code, as well as the original C# one, is practically unreadable. But it is interesting to note how the JS code could be simpler and readable if JS had do-notation (aka for-comprehensions).

Once it meets a branch in the original tree, the monadic labeler must enter in the context of the state monad(*) and:

  • resolve recursively the left branch (using implicitly the current state)
  • resolve recursively the right branch (using still impicitly the state from the left branch run)
  • compose the new pair-labeled branch and wrap it in the monad

Using a Haskell-like do-notation:

do
  // PLB = pair-labeled branch
  leftPLB <- monadicLabeler(left(branch))
  rightPLB <- monadicLabeler(right(branch))
return branch(leftPLB,rightPLB) // return === unit

JavaScript version:

branchSM = monadicLabeler(left(tree))
  .bind(function(leftPLB) { return monadicLabeler(right(tree))
    .bind(function(rightPLB) {
      return Monad.state.unit(branch(leftPLB,rightPLB));
    });
});

The bottom line is that Haskell remains probably the best tool for understanding these concepts.

(*) on the other hand, also the leaf production can be easily expressed in do-notation:

do
  n <- updateState
return leaf([n,tree()])

but this hides the working of updateState and is not useful to me as a learning aid.

Doing it imperatively

The state monad can be used to mimick an imperative syntax. Still all remaining pure and functional. All we have to do is use a list (for example, a JS array) as state and undefined as value. All what happens is state modifications.

The example in Haskell comes from this post (look for paragraph A Final Note About The State Monad with do Notation).

The state monad is:


\s -> do
        x <- pop
        pop
        push x

Assuming the initial state is a list [1,2,3,4,5], the intent is clearly to modify it to [1,2,3,5].

Again, no do-notation in JS; but we build a namespace ImperativeMonad for the experiment and we get to:


var imp = ImperativeMonad.pop.bind(function(x) {
    return ImperativeMonad.pop.bind(function(_) {
      return ImperativeMonad.push(x);
    });
});

The expression of push is given in the abovementioned post (in Haskell 😉 ). The JS translation is:


push = function(item) {
  return Monad.state.monad(function(state) {
    var stateCopy = state.slice();
    stateCopy.push(item);
    return {state:stateCopy,value:undefined};
  });
};

Given the item to stick in the state array, we build a monad that does just that.

The expression of pop ain’t given, but at this point the little bugger isn’t too hard to spot: we need a monad able to receive the state array, pop out its tail and ship that as the value. In pure words:


pop = Monad.state.monad(function(state) {
  var stateCopy, item;
  stateCopy = state.slice(),
  item = stateCopy.pop();
  return {state:stateCopy,value:item};
});

And so the test goes:

var result = imp([1,2,3,4,5]); // {state:[1,2,3,5],value:undefined}

Assert.areEqual(1, result.state[0]);
Assert.areEqual(2, result.state[1]);
Assert.areEqual(3, result.state[2]);
Assert.areEqual(5, result.state[3]);
Assert.areEqual(undefined, result.value);

Putting aside the fact that there are enough imperative programming environments around without having to build our own, this usage of the state monad seems to me just a Haskell antipattern (as little as I understand the matter).

Advertisements

One thought on “State monad goes to JS town (and starts swinging…)

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