The monad laws and state monad in JavaScript

UPDATE: This post has been updated to a new post. All the code has been refactored and redone in the new post. http://functionaljavascript.blogspot.in/2013/07/monads.html

In the previous post (please read the previous post before reading this post) we implemented three monads, the identity monad, maybe monad and array monad. However we did not get into the details of monads. We will do that in this post. Also we will implement the state monad. Here is an identity monad example.

var identityMonad = {
    mBind: function(mValue, mFunction) {
        return mFunction(mValue);
    },
    mResult: function(value) {
        return value;
    }
};

var result = doMonad(identityMonad,
    "a", function(scope) {
             return 2;
         },
    "b", function(scope) {
             with (scope) {
                 return a * 3;
             }
         },
    function(scope) {
        with(scope) {
            return a + b;
        }
    }
);

console.log(result);

First we define the identityMonad that we use when calling doMonad. Each computation in doMonad MUST return a monadic value. eg. the first computation returns 2 a monadic value. However what gets assigned to "a" is not the monadic value but the value. This distinction is important. However in the case of the identity monad both the monadic value and value are the same.

The mBind function takes a monadic value and a monadic function as its arguments. mBind then extracts the "value" out of the "monadic value" and calls the monadic function with the value. In this case no extraction is done because both are equal for the identity monad. The monadic function takes a "value" and returns a "monadic value".

In the next computation "a" is available as the value and not the monadic value. In the result computation both "a" and "b" are available and we return "value a + b". Since we return a value and not a monadic value in the final computation, the transformation from "value" to "monadic value" is done by the mResult function which takes a value and returns a monadic value. In this case it returns the argument itself because the value and monadic value are the same. So mResult is the identity function, and thats why it is called the identity monad.

We will look at a case where the "value" and "monadic value" are not the same. Using the array monad we will write a map function that doubles each element of an array.

var arrayMonad = {
    mBind: function(mValue, mFunc) {
        var accum = [];
        mValue.forEach(function(elem){
            accum = accum.concat(mFunc(elem));
        });
        return accum;
    },
    mResult: function(value) {
        return [value];
    }
};

var result = doMonad(arrayMonad,
    "i", function() {
            return [1, 2, 3];
         },
    function(scope) {
        with(scope) {
            return i * 2;
        }
    }
);

Running the above code will print the result [ 2, 4, 6 ]. The first function in doMonad returns a monadic value which is an array. However the "value" in a monadic value of array type is the value of each element. It is mBinds job to extract each value, and call the monadic function for each value, and thats what it does exactly.

The result function returns i * 2 which is of type integer. However all monadic functions of a given monad MUST return monadic values of the same type. It is mResults job to convert the result type from integer to array. And that is what it does exactly.

The monad laws

To write our own monads, our monads must obay the monad laws.

1) mBind(mResult(x), mFunction) is equal to mFunction(x).
2) mBind(mValue, mResult) is equal to mValue.
3) mBind(mBind(mValue, mFunction), mFunction2) is equal to
   mBind(mValue, function(x){return mbind(mFunction(x), mFunction2)}).

Now let us check to see if our array monad follows the monad laws.

var mBind = arrayMonad.mBind;
var mResult = arrayMonad.mResult;
var mValue = [1, 2, 3];
var x = 4;
var mFunction = function(x) {
    return [x * 2];
};
var mFunction2 = function(x) {
    return [x * 3];
};

// Check first law
console.log(mBind(mResult(x), mFunction));  // [ 8 ]
console.log(mFunction(x));  // [ 8 ]

//Check second Law
console.log(mBind(mValue, mResult));  // [ 1, 2, 3 ]
console.log(mValue);  // [ 1, 2, 3 ]

//Check third Law
console.log(mBind(mBind(mValue, mFunction), mFunction2));  // [ 6, 12, 18 ]
console.log(mBind(mValue, function(x){return mBind(mFunction(x), mFunction2)}));  // [ 6, 12, 18 ]

The State Monad

So far we saw monadic values of types integer and array. But monadic values can also be functions! After all JavaScript supports first class functions, that can be treated as values. The state monad is just such a monad. The monadic value is a function. However it is important to differentiate between a monadic function and a monadic value of type function.

The monadic function in a state monad, just like all monadic functions takes a value and returns a monadic value. It so happens that this monadic value is a function.

The monadic value in a state monad is a function that takes a state, and returns a two element array, with a value and the new state respectively. The state can be of any type. it can be a an integer, string, array object or any other valid type.

In the next example we maintain an immutable stack array over a set of computations. We define two monadic functions "push" and "pop".

var stateMonad = {
    mBind: function(mValue, mFunc) {
        return function(state) {
            var compute = mValue(state);
            var value = compute[0];
            var newState = compute[1];
            return mFunc(value)(newState);
        };
    },
    mResult: function(value) {
        return function(state) {
            return [value, state];
        };
    }
};

var push = function(value) {
    return function(state) {
        var newstate = [value];
        return [undefined, newstate.concat(state)];
    };
};

var pop = function() {
    return function(state) {
        var newstate = state.slice(1);
        return [state[0], newstate];
    };
};

var result = doMonad(stateMonad,
    "a", function(scope) {
             return push(5);
         },
    "b", function(scope) {
             with (scope) {
                 return push(10);
             }
         },
    "c", function(scope) {
             with (scope) {
                 return push(20);
             }
         },
    "d", function(scope) {
             with (scope) {
                 return pop();
             }
         },
    function(scope) {
        with(scope) {
            return d;
        }
    }
);

console.log(result([]));

Running the code above will print [ 20, [ 10, 5 ] ].

20 is the value of the last "pop" computation, and the second value is the final state of the stack.

First we will look at mResult. mResult is a monadic function that takes a value and returns a monadic value, which is a function that takes a state and returns an array with value and state.

mBind returns a monadic value which is a function. So the result of doMonad is a function which you must call with an initial value for the stack. Which is [] in our case. Remember mBind is called with a monadic value and a monadic function. It has to extract the value out of the monadic value and call the monadic function with the value. Which it does in the three lines inside the returned monadic function. Notice that mFunc is called with the extracted value, and since its return value is a monadic value of type function, the function is called immediately with the new state.

All the code in the last two posts are available as a monad library on github.