Sunday, April 14, 2013

The Promise 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

If you find it difficult to understand whats going on below, read the following posts.
Implementing Monads in JavaScript
The monad laws and state monad in JavaScript.

We will go through an example of the promise monad in this post. The promise monad is available now in the monadjs library. The best way is too look at an example. We will write a nodejs command line program that will copy an input file into an output file asynchronously. We can run the program like this.

$ node copy.js infile outfile

The program has to do the following.

  1. Check the command line for infile and verify it exists, if not print an error and halt computations.
  2. Check if outfile is given in the command line otherwise print error and halt.
  3. Read infile content into memory and halt if error.
  4. Write content to outfile or print error to console.
  5. Halting of program in case of error to be done without throwing errors.

Computations (1) (3) and (4) are asynchronous. (2) is synchronous because we are only checking process.argv.

The monadic values of the promise monad are functions that take a continuation and promise to call the continuation either asynchronously or synchronously. The continuation is called with a value which is the result of the last computation. If the continuation is called with "null" the computations are halted.

All the computations have access to the results of the previous computations via the "scope" variable. The results are stored in the variable names you give.
Here is the source code of copy.js

var monads = require("monadjs");
var fs = require("fs");

monads.doMonad(monads.promiseMonad,
    "infile",
        function(scope) {
            return function(continuation) {
                var fname = process.argv[2] || "";
                fs.exists(fname, function (exists) {
                    if (exists) {
                        continuation(fname);
                    } else {
                        console.log("File does not exist: " + fname);
                        continuation(null);
                    }
                });
            }
        },
    "outfile",
        function(scope) {
            return function(continuation) {
                var fname = process.argv[3];
                if (fname) {
                    continuation(fname);
                } else {
                    console.log("Output File Name is Required");
                    continuation(null);
                }
            }
        },
    "contents",
        function(scope) {
            return function(continuation) {
                fs.readFile(scope.infile, function (err, data) {
                    if (err) {
                        console.log("Error reading File: " + scope.infile);
                        continuation(null);
                    } else {
                        continuation(data);
                    }
                });
            }
        },
    function(scope) {
        fs.writeFile(scope.outfile, scope.contents, function (err) {
            if (err) {
                console.log("Error writing File: " + scope.outfile);
            }
        });
    }
);

I don't think the promise monad obeys the monad laws. But it works. It works only for sequential asynchronous calls though. What is interesting is that it allows you to break the program structure into bite size pieces and call them sequentially. Notice also the promise monad is implemented purely functionally, and no timing loops used.

However you don't have to actually use the promise monad from this library. I have refactored and simplified everything in a simple promise library you can find here.

Friday, April 5, 2013

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.