Friday, March 29, 2013

Implementing Monads 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

Consider the problem of doing a series of computations (calling a series of functions), and you want each successive computation to have access to the results of the previous computations. We will write a function called doComputations, and here is how a call to doComputations would look like.

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

The arguments to doComputaions are one or more "string - function" pairs and the last argument is just a "result" function. The string is a variable name which will be assigned the value returned from calling the function. So in the first case "a" will be assigned the value 2. What is interesting is that "a" is visible inside the next function whose value gets assigned to "b". And both "a" and "b" are visible inside the last function. Every function is called with a "scope" object which carries key value pairs corresponding to the previous computations carried out. Here we use the "with" statement to scope the "scope" object within the function. If you don't want to use the "with" statement you could access the variable from the scope object directly eg. scope.a, scope.b. The value returned by doComputations is the value returned by the last "result" function, in this case the final value is 8. And here is the definition of doComputations.

function doComputations() {
    var args = arguments;
    var scope = {};
    function iterator(i) {
        if (args.length === i + 1) {return args[i](scope);}
        var varName = args[i];
        var func = args[i + 1];
        var value = func(scope);
        scope[varName] = value;
        return iterator(i + 2);
    }
    return iterator(0);
}

Inside doComputations we define an iterator function, which recursively iterates over the arguments array of doComputations. In the first line of the iterator function we check to see if we have reached the last "result function", if yes we call it with scope and return the result. In the next three lines we create three variables initialised to the variable name, function, and value returned by calling the function with the scope. In the next line we attach the key-value to scope. And finally we make a recursive call to the iterator to do the next computation. In the last line of doComputations we start the iterator with initial values 0 for the index.

Copy the two code fragments above into a file, add the a final line:
console.log(result);
and run it. You should get the result as 8.

All this looks like lots of work just to add and multiply a couple of integers, but we have done something useful. For one we have abstracted away the nitty gritty of iterating over computations, with visibility of previous results, into a function called doComputations.

Computations are not always so simple and straight forward as the one above. What if we wanted to abort the computations midway for some reason? eg. If any of the functions returns "null" we want to abort the computations. There are many other types of computations and to write a version of doComputations for each type is not a good idea. Instead we could make doComputations call another function between computations so that any thing different, we want to do, is done in this function. This function is passed to doComputations as its first argument. We will call this function "mBind". Now all we have to do is write a version of mBind for every type of computation. For every computation, doComputations will call mBind which in turn will call the next computation. First we write the mBind function to handle null values returned by any computation.
var mBind = function(mValue, mFunction) {
    if (mValue === null)
        return null;
    else
        return mFunction(i + 2);
}

Now the iterator function will call mBind, which is passed as an argument to doComputations, which in turn will recursively call the iterator.

function doComputations(mBind) {
    var args = arguments;
    var scope = {};
    function iterator(i) {
        if (args.length === i + 1) {return args[i](scope);}
        var varName = args[i];
        var func = args[i + 1];
        var value = func(scope);
        return mBind(value, function() {
            scope[varName] = value;
            return iterator(i + 2);
        });
    }
    return iterator(1);
}

Below we call doComputations whose first argument is the mBind function. Also we want to abort the computations in case the browser does not support the console.log function.

var result = doComputations(mBind,
    "a", function(scope) {
         if (typeof console === "object" && console.log)
             return 2;
         else
             return null;
         },
    "b", function(scope) {
          with (scope) {
                 return a * 3;
             }
         },
    function(scope) {
        with(scope) {
            return a + b;
        }
    }
);

We can now use doComputations for various types of computations by simply changing the mBind function passed to it. It would be even better if we could predefine the mBind function for various types of computations. And that is what we will do below. We will also change the name of doComputations to doMonad. And we will add mBind as the property of an object called "monad".

var maybeMonad = {
    mBind: function(mValue, mFunction) {
        if (mValue === null)
            return null;
        else
            return mFunction(mValue);
    }
};

function doMonad(monad) {
    var args = arguments;
    var scope = {};
    function iterator(i) {
        if (args.length === i + 1) {return args[i](scope);}
        var varName = args[i];
        var func = args[i + 1];
        var value = func(scope);
        return monad.mBind(value, function() {
            scope[varName] = value;
            return iterator(i + 2);
        });
    }
    return iterator(1);
}

Compare the above code to the previous listing. It is pretty much the same, except that we have renamed doComputations, and the mBind function is now passed as the property of an object, and this object is called a monad, and in this specific case we called the monad the "maybeMonad". Because "maybe" the computations are carried out, or "maybe" they won't be.

A monad MUST have two properties defined for it to be a proper monad. "mBind" and "mResult". We have not seen mResult so far. mResult is a wrapper function for the "result" function. So we add support for mResult in doMonad below. Also we define a new monad called the arrayMonad below and we do some computations with the it.

function doMonad(monad) {
    var args = arguments, scope = {};
    function iterator(i) {
        if (args.length === i + 1) {
            return monad.mResult(args[i](scope));
        }
        var varName = args[i];
        var func = args[i + 1];
        var value = func(scope);
        return monad.mBind(value, function(value) {
            scope[varName] = value;
            return iterator(i + 2);
        });
    }
    return iterator(1);
}

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,
    "a", function() {
             return [1, 2];
         },
    "b", function() {
             return [3, 4];
         },
    function(scope) {
        with(scope) {
            return a + b;
        }
    }
);

console.log(result);

Running the code above will yield a result of [ 4, 5, 5, 6 ]. The computations using the arrayMonad each return an array. The final result function is called with values a and b, for each element of both arrays. ie it will be called with (1,3), (1,4), (2,3), (2,4). And the addition of each of the elements yields the returned array of [ 4, 5, 5, 6 ].

Using the arrayMonad let us implement a two dimensional iterator function in JavaScript called forEach2D. It will take 3 arguments, an iArray, a jArray, and a callback. The callback is called for each value of i and j. Here is the code below.

function forEach2D(iArray, jArray, callback) {
    return doMonad(arrayMonad,
        "i", function() {
                 return iArray;
             },
        "j", function() {
                 return jArray;
             },
        function(scope) {
            with(scope) {
                return callback(i, j);
            }
        }
    );
}

var result = forEach2D([1, 2, 3], [4, 5, 6], function(i, j) {
    return [i, j];
});

console.log(result);
Running the code above will yield result:
[ [1, 4],[1, 5],[1, 6],[2, 4],[2, 5],[2, 6],[3, 4],[3, 5],[3, 6] ]

How about a function for iterating over three arrays? A forEach3D function. Easy!

function forEach3D(iArray, jArray, kArray, callback) {
    return doMonad(arrayMonad,
        "i", function() {
                 return iArray;
             },
        "j", function() {
                 return jArray;
             },
        "k", function() {
                 return kArray;
             },
        function(scope) {
            with(scope) {
                return callback(i, j, k);
            }
        }
    );
}

var result = forEach3D([1, 2], [3, 4], [5, 6], function(i, j, k) {
    return [i, j, k];
});

console.log(result);
And running this code will print out:
[ [1, 3, 5], [1, 3, 6], [1, 4, 5], [1, 4, 6], [2, 3, 5], [2, 3, 6], [2, 4, 5], [2, 4, 6] ]

You can begin to see the power of monads here. They abstract away the complicated part of your code and simplify the problem at hand. Monads are a hard concept to understand, and I hope that I have simplified its understanding here. If there is any part not clear enough please let me know. In the next post I hope to take a more in depth look and monads with some interesting examples.

No comments:

Post a Comment

Post a Comment