Thursday, July 25, 2013

Monads

Monads

All the code for this post are available here.https://github.com/santoshrajan/monadjs

Consider the map functor from the last chapter. We could use map to iterate over two arrays adding each element of the first to the second.

var result = [1, 2].map(function(i) {
    return [3, 4].map(function(j) {
       return i + j
    })
})
console.log(result)     ==>>  [ [ 4, 5 ], [ 5, 6 ] ]

The type signature of the inner function is

f: int -> int

and the type signature of the inner map is

map: [int] -> [int]

The type signature of the outer function is

f: int -> [int]

and the type signature of the outer map is

map: [int] -> [[int]]

This is the right behaviour you would expect from a functor. But this is not what we want. We want the result to be flattened like below.

[ 4, 5, 5, 6 ]

Array Monad

For that to happen, the type signature of a functor should always be restricted to

F: [int] -> [int]

But functors do not place any such restriction. But monads do. The type signature of an array monad is

M: [T] -> [T]

where T is a given type. That is why map is a functor but not a monad. That is not all. We have to put some type restriction on the function passed it too. The function cannot return any type it likes. We can solve this problem by restricting the function to return the Array type. So the function's type signature is restricted to

f: T -> [T]

This function is known as lift, Because it lifts the type to the required type. This is also known as the monadic function. And the original value given to the monad is known as the monadic value. Here is the arrayMonad.

function arrayMonad(mv, mf) {
    var result = []
    mv.forEach(function(v) {
        result = result.concat(mf(v))
    })
    return result
}

Now we can use the array monad to do our first calculation.

console.log(arrayMonad([1,2,3], function(i) {
    return [i + 1]
}))                                       ==>>  [ 2, 3, 4 ]

Notice that our monadic function wraps the result in an array [i + 1]. Now let us try it with the two dimensional problem we started with.

var result = arrayMonad([1, 2], function(i) {
    return arrayMonad([3, 4], function(j) {
        return [i + j]
    })
})
console.log(result)                      ==>>  [ 4, 5, 5, 6 ]

Now we begin to see the power of monads over functors.

We can write a generic two dimensional iterator for arrays which will take two arrays and a callback, and call it for each element of both arrays.

function forEach2d(array1, array2, callback) {
    return arrayMonad(array1, function(i) {
        return arrayMonad(array2, function(j) {
            return [callback(i,j)]
        })
    })
}

And we can try this function

forEach2d([1, 2], [3,4], function(i, j) {
    return i + j
})                                     ==>> [ 4, 5, 5, 6 ]

Notice that the callback function is just a regular function, so we had to lift its return value [callback(i,j)] to an array. However all monads define a function to do the lifting. Its called mResult. We will add mResult to the arrayMonad function object. Also the concat function is inneficient as it creates a new array everytime. We will apply array push instead. Here is the final code for the array monad.

function arrayMonad(mv, mf) {
    var result = []
    mv.forEach(function(v) {
        Array.prototype.push.apply(result, mf(v))
    })
    return result
}

arrayMonad.mResult = function(v) {
    return [v]
}

and rewrite forEach2d

function forEach2d(array1, array2, callback) {
    return arrayMonad(array1, function(i) {
        return arrayMonad(array2, function(j) {
            return arrayMonad.mResult(callback(i,j))
        })
    })
}

As an exersice I will leave it to the reader to implement forEach3d.

The arrayMonad is a monadic function and is otherwise known as bind or mbind. For a function to be a monad it must define atleast the functions mbind and mresult.

Identity Monad

The identity monad is the simplest of all monads, named so because it's mresult is the identity function.

function indentityMonad(mv, mf) {
    return mf(mv)
}

identityMonad.mResult = function(v) {
    return v
}

It is not a very useful monad. But it is a valid monad.

Maybe Monad

The maybe Monad is similar to the identity monad, except that it will not call the monadic function for values null or undefined. In fact it boild down to the same mayBe functor we saw in the last chapter.

function mayBeMonad(mv, mf) {
    return mv === null || mv === undefined || mv === false ? null : mf(mv)
}

mayBeMonad.mResult = function(v) {
    return v
}

The Monad Laws

The First Monad Law

M(mResult(x), mf) = mf(x)

Which means whatever mResult does to x to turn x into a monadic value, M will unwrap that monadic value before applying it to monadic function mf. Let us test this on our array monad.

var x = 4;  
function mf(x) {  
    return [x * 2]  
}
arrayMonad(arrayMonad.mResult(x), mf)  ==>>  [ 8 ]
mf(x)                                  ==>>  [ 8 ]

The Second Monad Law

M(mv, mResult) = mv

Which means whatever mBind does to extract mv's value, mResult will undo that and turn the value back to a monadic value. This ensures that mResult is a monadic function. Let us test it. This is equivalent to the preserve identity case of the functor.

arrayMonad([1, 2, 3], arrayMonad.mResult)  ==>>  [ 1, 2, 3 ]

The Third Monad Law

M(M(mv, mf), mg)) =  M(mv, function(x){return M(mf(x), mg)})

What this is saying is that it doesn't matter if you apply mf to mv and then to mg, or apply mv to a monadic function that is a composition of mf and mg. Let us test this.

function mg(x) {
    return [x * 3]
}
arrayMonad(arrayMonad([1, 2, 3], mf), mg)  ==>>  [ 6, 12, 18 ]
arrayMonad([1, 2, 3], function(x) {
    return arrayMonad(mf(x), mg)
})                                         ==>>  [ 6, 12, 18 ]

doMonad

We know that a monadic function takes a value and returns a monadic value. A monad takes a monadic value and a monadic function and returns a monadic value. What if a monadic function calls a monad with a monadic value and itself and returns the result? That would be a valid monadic function because it returns a monadic value.

The function doMonad does exactly this. It takes a monad and an array of monadic values and a callback as its arguments. It defines a monadic function that recursively calls the monad with each monadic value and itself. It breaks out of the loop when there are no more monadic values left. It returns the callback called with each unwrapped value of the monadic value. The callback cb is curried in a closure called wrap and is visible to mf. The curry function is from the chapter on currying.

function curry(fn, numArgs) {
    numArgs = numArgs || fn.length
    return function f(saved_args) {
        return function() {
            var args = saved_args.concat(Array.prototype.slice.call(arguments))
            return args.length === numArgs ? fn.apply(null, args) : f(args)
        }
    }([])
}

function doMonad(monad, values, cb) {
    function wrap(curriedCb, index) {
        return function mf(v) {
            return (index === values.length - 1) ?
                monad.mResult(curriedCb(v)) :
                monad(values[index + 1], wrap(curriedCb(v), index + 1))
        }
    }
    return monad(values[0], wrap(curry(cb), 0))       
}
doMonad(arrayMonad, [[1, 2], [3, 4]], function(x, y) {
    return x + y
})                           //==>> [ 4, 5, 5, 6 ]

We don't need the forEach2d function we wrote earlier! And the best is yet to come!

Array comprehension using doMonad

We can write a generic array comprehension function called FOR which takes a set of arrays and a callback in its arguments.

function FOR() {
    var args = [].slice.call(arguments)
        callback = args.pop()
    return doMonad(arrayMonad, args, callback)
}

FOR([1, 2], [3, 4], function(x, y) {
    return x + y
})                          //==>> [ 4, 5, 5, 6 ]
FOR([1, 2], [3, 4], [5, 6], function(x, y, z) {
    return x + y + z
})                          //==>> [ 9, 10, 10, 11, 10, 11, 11, 12 ]

How awesome is that!

State Monad

In the last chapter on functors we saw function fucntor that takes a value of type function. Similarly monadic values can also be functions. However it is important to distinguish between monadic functions and monadic values that are functions. The type signature of a monadic function is

mf: v -> mv

ie. takes a value and lifts it to a monadic value. Note that the monadic value itself is a function. So mf will return a function mv.

The type signature of a monadic value which is a function depends on whatever that function is doing as the case may be. In the case of the state monad the type signature of its monadic value is

mv: state -> [value, new state]

The monadic value function takes a state and returns an array containing a value and a new state. The state can be of any type array, string, integer, anything.

The stateMonad takes a monadic value and a monadic function and returns a function to which we have to pass the initial state. The initial state is passed mv which returns a value. mf is then called with this value and mf returns a monadic value which is a function. We must call this function with the newstate. Phew!

function stateMonad(mv, mf) {  
    return function(state) {  
        var compute = mv(state)  
        var value = compute[0]  
        var newState = compute[1]  
        return mf(value)(newState)  
    } 
}

And mResult for the state monad is

stateMonad.mResult = function(value) {  
    return function(state) {  
            return [value, state];  
    }  
}

Parser Monad

A parser is function that takes a string matches the string based on some criteria and returns the matched part and the remainder. Lets write the type signature of the function.

parser: string -> [match, newstring]

This looks like the monadic value of the state monad, with state restricted to the type string. But thats not all, the parser will return null if the string did not match the criteria. So lets write the parser monad to reflect the changes.

function parserMonad(mv, mf) {  
    return function(str) {  
        var compute = mv(str)
        if (compute === null) {
            return null
        } else {
            return mf(compute[0])(compute[1])
        }  
    } 
}

parserMonad.mResult = function(value) {  
    return function(str) {  
        return [value, str];  
    }  
}

As we saw earlier Monads require you to define atleast two functions, mBind (the monad function itself) and mResult. But that is not all. Optionally you can define two more functions, mZero and mPlus.

mZero is the definition of "Nothing" for the monad. eg. for the arrayMonad, mZero would be []. In the case of the parser monad mZero is defined as follows. (mZero must have the same type signature of the monadic value).

parserMonad.mZero = function(str) {
    return null
}

mPlus is a function that takes monadic values as its arguments, and ignores the mZero's among them. How the accepted values are handled depends on the individual monad. For the parser monad, mZero will take a set of parsers (parser monad's monadic values) and will return the value returned by the first parser to return a non mZero (null) value.

parserMonad.mPlus = function() {
    var parsers = Array.prototype.slice.call(arguments)
    return function(str) {
        var result, i
        for (i = 0; i < parsers.length; ++i) {
            result = parsers[i](str)
            if (result !== null) {
                break;
            }
        }
        return result
    }
}

Continuation Monad

The continuation monad takes a bit to understand. In the chapter on function composition we saw that the composition of two functions f and g is given by

(f . g) = f(g(x))

f is known as the continuation of g.

We also know that we can wrap values in a function by creating a closure. In the example below the inner function has a value wrapped in its closure.

function(value) {
    return function() {
        // value can be accessed here
    }
} 

The monadic value of a continuation monad, is a function that takes a continuation function and calls the continuation with its wrapped value. This is just like the inner function above called with a continuation function and we we can write it as

function(continuation) {
    return continuation(value)
}

The mResult function of monad takes a value and lifts it to a monadic value. So we can write the mResult function for the continuation monad.

var mResult = function(value) {
    return function(continuation) {
        return continuation(value)
    }
}

So mResult is a function that takes a value, returns a monadic value which you call with a continuation.

The continuation monad itself or mBind is more complicated.

var continuationMonad = function(mv, mf) {
    return function(continuation) {
         // we will add to here next
    }
}

First it will return a function you need to call with a continuation. Thats easy. But how can it unwrap the value inside mv? mv accepts a continuation, but calling mv with the continuation will not do. We need to unwrap the value in mv and call mf first. So we need to trick mv into giving us the value first by calling it with our own continuation thus.

mv(function(value) {
    // gotcha! the value
})

We can add this function to the code above.

var continuationMonad = function(mv, mf) {
    return function(continuation) {
        return mv(function(value) {
            // gotcha! the value
        })
    }
}

Now all we have to do is call mf with the value. We know a monadic function takes a value and returns a monadic value. So we call the returned monadic value from mf with the continuation. Phew! Here is the complete code for the continuation monad.

var continuationMonad = function(mv, mf) {
    return function(continuation) {
        return mv(function(value) {
            return mf(value)(continuation)
        })
    }
}
continuationMonad.mResult = function(value) {
    return function(continuation) {
        return continuation(value)
    }
}

Tuesday, July 16, 2013

Functors

Consider the function below.

function plus1(value) {  
    return value + 1  
}  

It is just a function that takes an integer and adds one to it. Similarly we could could have another function plus2. We will use these functions later.

function plus2(value) {  
    return value + 2  
}  

And we could write a generalised function to use any of these functions as and when required.

function F(value, fn) {  
    return fn(value)  
}

F(1, plus1) ==>> 2

This function will work fine as long as the value passed is an integer. Try an array.

F([1, 2, 3], plus1)   ==>> '1,2,31'

Ouch. We took an array of integers, added an integer and got back a string! Not only did it do the wrong thing, we ended up with a string having started with an array. In other words our program also trashed the structure of the input. We want F to do the "right thing". The right thing is to "maintain structure" through out the operation.

So what do we mean by "maintain structure"? Our function must "unwrap" the given array and get its elements. Then call the given function with every element. Then wrap the returned values in a new Array and return it. Fortunately JavaScript just has that function. Its called map.

[1, 2, 3].map(plus1)   ==>> [2, 3, 4]

And map is a functor!

A functor is a function, given a value and a function, does the right thing.

To be more specific.
A functor is a function, given a value and a function, unwraps the values to get to its inner value(s), calls the given function with the inner value(s), wraps the returned values in a new structure, and returns the new structure.

Thing to note here is that depending on the "Type" of the value, the unwrapping may lead to a value or a set of values.

Also the returned structure need not be of the same type as the original value. In the case of map both the value and the returned value have the same structure (Array). The returned structure can be any type as long as you can get to the individual elements. So if you had a function that takes and Array and returns value of type Object with all the array indexes as keys, and corresponding values, that will also be a functor.

In the case of JavaScript, filter is a functor because it returns an Array, however forEach is not a functor because it returns undefined. ie. forEach does not maintain structure.

Functors come from category theory in mathematics, where functors are defined as "homomorphisms between categories". Let's draw some meaning out of those words.

  • homo = same
  • morphisms = functions that maintain structure
  • category = type

According to the theory, function F is a functor when for two composable ordinary functions f and g

F(f . g) = F(f) . F(g)

where . indicates composition. ie. functors must preserve composition.

So given this equation we can prove wether a given function is indeed a functor or not.

Array Functor

We saw that map is a functor that acts on type Array. Let us prove that the JavaScript Array.map function is a functor.

function compose(f, g) {
    return function(x) {return f(g(x))}
}

Composing functions is about calling a set of functions, by calling the next function, with results of the previous function. Note that our compose function above works from right to left. g is called first then f.

[1, 2, 3].map(compose(plus1, plus2))   ==>> [ 4, 5, 6 ]

[1, 2, 3].map(plus2).map(plus1)        ==>> [ 4, 5, 6 ]

Yes! map is indeed a functor.

Lets try some functors. You can write functors for values of any type, as long as you can unwrap the value and return a structure.

String Functor

So can we write a functor for type string? Can you unwrap a string? Actually you can, if you think of a string as an array of chars. So it is really about how you look at the value. We also know that chars have char codes which are integers. So we run plus1 on every char charcode, wrap them back to a string and return it.

function stringFunctor(value, fn) {  
    var chars = value.split("")  
    return chars.map(function(char) {  
        return String.fromCharCode(fn(char.charCodeAt(0)))  
    }).join("")  
}

stringFunctor("ABCD", plus1) ==>> "BCDE"  

You can begin to see how awesome functors are. You can actually write a parser using the string functor as the basis.

Function Functor

In JavaScript functions are first class citizens. That means you can treat functions like any other value. So can we write a functor for value of type function? We should be able to! But how do we unwrap a function? You can unwrap a function by calling it and getting its return value. But we straight away run into a problem. To call the function we need its arguments. Remember that the functor only has the function that came in as the value. We can solve this by having the functor return a new function. This function is called with the arguments, and we will in turn call the value function with the argument, and call the original functors function with the value returned!

function functionFunctor(value, fn) {  
    return function(initial) {  
        return function() {  
            return fn(value(initial))  
        }  
    }  
}

var init = functionFunctor(function(x) {return x * x}, plus1)  
var final = init(2)  
final() ==> 5

Our function functor really does nothing much, to say the least. But there a couple things of note here. Nothing happens until you call final. Every thing is in a state of suspended animation until you call final. The function functor forms the basis for more awesome functional stuff like maintaining state, continuation calling and even promises. You can write your own function functors to do these things!

MayBe Functor

function mayBe(value, fn) {
    return value === null || value === undefined ? value : fn(value)
}

Yes, this is a valid functor.

mayBe(undefined, compose(plus1, plus2))     ==>> undefined
mayBe(mayBe(undefined, plus2), plus1)       ==>> undefined
mayBe(1, compose(plus1, plus2))             ==>> 4
mayBe(mayBe(1, plus2), plus1)               ==>> 4

So mayBe passes our functor test. There is no need for unrapping or wrapping here. It just returns nothing for nothing. Maybe is useful as a short circuiting function, which you can use as a substitute for code like

if (result === null) {
    return null
} else {
    doSomething(result)
}

Identity Function

function id(x) {
    return x
}

The function above is known as the identity function. It is just a function that returns the value passed to it. It is called so, because it is the identity in composition of functions in mathematics.

We learned earlier that functors must preserve composition. However something I did not mention then, is that functors must also preserve identity. ie.

F(value, id) = value

Lets try this for map.

[1, 2, 3].map(id)    ==>>  [ 1, 2, 3 ]

Type Signature

The type signature of a function is the type of its argument and return value. So the type signature of our plus1 function is

f: int -> int

The type signature of the functor map depends on the type signature of the function argument. So if map is called with plus1 then its type signature is

map: [int] -> [int]

However the type signature of the given function need not be the same as above. We could have a function like

f: int -> string

in which the type signature of map would be

map: [int] -> [string]

The only restriction being that the type change does not affect the composability of the functor. So in general a functor's type signature can

F: A -> B

In other words map can take an array of integers and return an array of strings and would still be a functor.

Monads are a special case of Functors whos type signature is

M: A -> A

More about monads in the next chapter.

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.

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.

Wednesday, March 27, 2013

Introduction to Functional JavaScript

JavaScript was a functional programming language even before it got its name! Back in 1995 Netscape Communications the makers of the Netscape Browser realized that their browser needed a scripting language embedded in HTML. They hired Brendan Eich to embed the Scheme programming language in HTML. Scheme was a full fledged functional programming language. To his dismay “the powers that be” encouraged Brendan to come up with a more traditional programming language. His first cut was a language called “Mocha” in May 1995, and it retained that name till December 1995. It was first renamed “LiveScript” and soon after that Netscape and Sun did a license agreement and it was called “JavaScript”. But by then Brendan Eich had sneaked in some “functional programming” features into JavaScript.

The story gets more complicated, and we will delve into it. Because this story will tell you why JavaScript is what it is today. Brendan Eich claims that hiring him to embed the Scheme language, might actually have been a “bait and switch operation”. But at that point in time Netscape was also negotiating with Sun to embed Java in the browser. Note that JavaScript was for embedding in HTML while Java was for embedding in the Browser. The idea was that Java would be used for component development while JavaScript would be used for lightweight scripting within HTML.

We don't know what actually transpired, but the orders from above to Brendan where clear. The new scripting language must “look like Java” and must be “object based”. Any hopes Brendan might have harboured for Scheme, where now out of the window. We will see why.

Programming Paradigms

We can only speculate on what “look like Java” meant. However we can be certain that it had to be a “curly brace” language. Curly brace languages define statement blocks using curly braces, the “{“ and “}” characters. Indeed Java syntax was fashioned on another curly brace language “C++”, which in turn was fashioned on “C”. Here is how a for-loop looks in Java.

for (int i = 0; i < 10; i++) {
    System.out.println("Hello");
    System.out.println("World");
}
The same for-loop in C.
int i;
for (i = 0; i < 10; i++) {
    printf("Hello\n");
    printf("World\n");
}
And the for-loop in JavaScript.
for (var i = 0; i < 10; i++) {
    console.log("Hello");
    console.log("World");
}

Indeed JavaScript does look like Java. And C too. However curly braces where not the only implications for a language to “look like Java”. Java is an imperative/object oriented style programming language. JavaScript also had to be an imperative/object oriented style language.

Programming languages are made up of operators, conditional statements, loop statements and functions. Having conditional statements and loop statements are hallmarks of an “imperative” style programming language. Functional style languages tend to support operators and functions only.

It is interesting that none of the three languages, Java, C++ and C, were functional programming languages. While C was an imperative programming language, C++ and Java were Imperative/Objected Oriented programming languages. By now you would have guessed that the three programming paradigms (styles) were imperative, object oriented and functional. There is one more, the declarative paradigm.

The differences between these paradigms are because of the foundations on which they were based. Imperative and object oriented programming are based on the “turing machine”. Functional programming is based on “lambda calculus” and declarative programming is based on “first order logic”. In this post we will look at the differences between, imperative, object oriented and functional programming at a more practical level.

An imperative programming language is one in which program state change is achieved by executing a series of statements, and does flow control primarily using conditional statements, loop statements and function calls. The program given below is a simple implementation of the JavaScript Array.join method in an imperative manner.

function simpleJoin(stringArray) {
    var accumulator = '';
    for (var i=0, l=stringArray.length; i < l; i++) {
        accumulator = accumulator + stringArray[i];
    }
    return accumulator;
}

The code above is straight forward. We iterate through an array and add each string element to the accumulator and return the accumulator. We will now rewrite this function in an object oriented manner. Since JavaScript has an Array class, we will add this method to the Array class, so that every instance of this class has access to this function. JavaScript use prototypal inheritance and so we add this function to the Array prototype.

Array.prototype.simpleJoin = function() {
    var accumulator = "";
    for (var i=0, l=this.length; i < l; i++) {
        accumulator = accumulator + this[i];
    }
    return accumulator;
}

As we can see, the object oriented version is quite like the imperative version, except that the function (method) is now a method of the class. Object oriented languages tend to be imperative languages also.

Now let us write the functional version of this function.
function simpleJoin(stringArray, i, accumulator) {
    if (i === stringArray.length) {
     return accumulator;
    } else {
     return simpleJoin(stringArray, i+1, accumulator+stringArray[i])
    }
}

The first thing to note is that we are not using the for loop here for iteration. Instead we use recursion for iteration. Recursion happens when the function calls itself from within itself. Indeed this is one of the characteristics of a functional programming language. eg. Scheme does not have any loop statements. Instead it uses recursion for iteration. The function is called for the first time with the given array in stringArray, i set to 0, and accumulator set to "". The second time around the function is called from within itself with the same stringArray, i set to i + 1, and accumulator set to accumulator + stringArray[i]. And we continue the same way until i === stringArray.length when we return the accumulator. We will discuss recursion in detail later in a later post. Just remember we used recursion for doing iteration here.

There is still something imperative about this function. The if statement. Functional languages tend to use expressions that evaluate to some value, instead of statements that don't evaluate to anything. So let us rewrite the function, to make it as functional as possible in JavaScript.

function simpleJoin(stringArray, i, accumulator) {
    return (i === stringArray.length) ? accumulator :
        simpleJoin(stringArray, i + 1, accumulator + stringArray[i])
}

Now this as functional as you can get with JavaScript. Instead of the if statement we return the value evaluated by the conditional operator ?. The conditional operator ? Takes a conditional expression and returns the value of one of the two expressions based the condition being true or false. The value of the first expression is returned if true and the second if false.

We can see that the functional version is concise. Indeed one of the advantages of functional programming is that it lends itself to lesser code to accomplish the same thing, leading to better readability and maintainability.

However in the case of JavaScript, as of now you cannot use recursion for doing iteration. You should continue to use the imperative or object oriented method for iteration. This is because JavaScript does not (yet) support “tail call optimization”. For doing proper recursion, tail call optimization is required. We will discuss tail recursion, and tail call optimization, and how to get around this problem in a future post. As of writing this post tail call optimization is expected in ecmascript 6.

So is JavaScript an imperative language, or an object oriented language, or a functional language? It is a multi paradigm language. It does not have all the functional features implemented. But it is slowly getting there. This is also true of most other languages. Most languages (other than functional languages to begin with) have added functional features to various degrees over the years. A good example of the multi paradigm nature of JavaScript is the Array.forEach method. Here is a possible simple implementation. Note that all modern browsers have already implemented this.

Array.prototype.forEach = function(callback) {
    for (var i = 0, len = this.length; i < len; ++i) {
        callback(this[i], i, this);
    }
}

In the code above the for-loop part of the code is imperative. Adding to the array prototype and usage of this is object oriented. Passing a function as an argument to another function (callback) is functional and is a feature of functional programming known as “higher order function”. In JavaScript, we take this for granted, passing functions as an argument. Surprisingly this was not a feature found in the most popular languages until recently. eg. You cannot pass functions as arguments in Java, though you can do it indirectly via Interfaces. Same is the case with C, though you can do it indirectly using pointers.

Programming Abstractions

What if JavaScript did not have the “passing functions as arguments feature”? The answer to this question is crucial to understanding what functional programming brings to the table. For one, we would not be able to write the Array.forEach function above. And even worse, every time we had to iterate over an array, we would have to write the same for-loop again and again. If we had Array.foreach we need to think only about writing the callback. We need to think only of what to do with each element of the array, and need not concern ourselves with iterating over the array. In other words we have “abstracted” away the iteration part of the problem, and freed ourselves to concentrate on each element of the array.

Abstractions are about hiding away implementation details, thereby reducing and factoring out details, so that programmers can focus on the problem at a higher level. Abstractions can be code abstractions, as we saw in the example above, and data abstractions. Objected oriented programming is about combining code and data abstractions into one abstraction called the class. In functional programming we use functional features like first class functions, nested functions, anonymous functions and closures to abstract away code and sometimes even data. Monads are an esoteric feature of functional programming that can even abstract away program structure!

Macro's are another feature that allows code abstraction. However macros are not a feature of functional programming. But they are found in all Lisp like functional languages like Lisp, Scheme, Clojure etc. There are attempts to bring Macro's to JavaScript and at the moment it is very much early days.

A good example of the power of functional abstractions is jQuery. jQuery is the mother of all functional abstractions. It has abstracted away the JavaScript language itself! So much so that you wouldn't be surprised, if you found a jQuery programmer who knows very little or no JavaScript. As of Feb 2013 there was one publisher who had 32 jQuery books listed, and not a single JavaScript book! And jQuery has achieved so much mostly using only two functional features, functions as arguments and closures.

First Class Functions and Closures

The functional programming feature that Brendan Eich implemented in JavaScript was “first class functions”. Functions are first class if they are treated as “first class citizens” of that language. Which implies functions are treated just like all other variables. ie. You can pass them as arguments to functions, you can return them as values from other functions, or you can assign them to variables or data structures. We have seen “passing functions are arguments” earlier. Here is an example of assigning a function to a variable.

function greet(name) {
    console.log("Hello " + name);
}

greet("John"); // "Hello John"

var sayHello = greet;
sayHello("Alex"); // "Hello Alex"

Some programming language theorists consider “anonymous functions” as first class functions. Not to be outdone, Brendan Eich threw anonymous functions into the mix. This is like letting the cat among the pigeons so to speak. But not for Brendan Eich, he knew the solution to the problem. Here is an anonymous function in JavaScript.

function(name) {
    console.log(“Hello “ + name);
}

If you noticed we did not give this function a name. After all, it is an anonymous function. If you try to run the code above, you will get an error. Something to the effect “you cannot run the code in this context”. And rightly so. They can only be assigned to something, or passed as arguments to a function.

var sayHello = function(name) {
    console.log(“Hello “ + name);
}
sayHello("Jane"); // "Hello Jane"

What if we wanted to change the greeting? Sometimes we would like to say “Hi” instead of “Hello”. We could create a generic “createGreeting” function, which would in turn “compose” another function for you, and return the new composed function. So if we wanted to sat “Hi” it would return a function, and if we wanted to say “Hello” it would return another function that says “Hello”. We can do all that because JavaScript supports first class functions, and we can return functions from other functions. Here is the code.

function createGreeting(greeting) {
    return function(name) {
        console.log(greeting + " " + name);
    }
}
var sayHi = createGreeting("Hi");
sayHi("Jack"); // "Hi Jack"
var sayHello = createGreeting("Hello");
sayHello("Jack"); // "Hello Jack"

The createGreeting function takes a greeting as its argument. The function returns a newly created anonymous function. However the newly created anonymous function was created inside another function createGreeting. So it is also a nested function now. Now since our language supports anonymous functions it will also have to support nested functions. And when we return nested functions from our function we run into another problem. We will look at that in more detail.

The anonymous function takes a name argument and prints to the console greeting + name. The variable name is an argument to the anonymous function, and behaves just like any other variable defined within the function. In other words name is “local” to the anonymous function. But this is not true of the variable greeting. It is defined in another function called createGreeting and hence is “non local” to the anonymous function. However the anonymous function can access the variable greeting due to something called lexical scoping.

The “scope” of a variable is its “visibility” within a program. “Lexical scope” means that visibility is limited to all the text (code). So when we say “local variables are lexically scoped” within a function, it means that the function's local variables are visible to all the text (code) in the function, even if the code is within another nested function. This also means that when you run the nested function outside the lexically scoped environment, the nested functions non local variable will not be visible. And there lies the problem of returning nested functions from another function. And indeed thats what we are doing here.

var sayHi = createGreeting("Hi");

In the line above we assign the returned anonymous function to variable sayHi. And call the function in the next line.

sayHi(“Jack”)

We are calling sayHi outside of createGreeting. And the greeting variable is not available outside of createGreeting. The variables it may access in the scope where it was defined, may not be available in the scope where it was actually called. Thats why languages like C don't support nested functions. For this to work the language needs to support another functional programming feature called “closures”. JavaScript supports closures. As matter of fact it has to support closures. Any language that supports first class functions and nested functions has to support closures.

A function's closure is a reference to all its non local variables. In the previous example greeting was the non local variable and name was the local variable. A closure is a table of references to all of a functions non local variables. This allows the function to continue to refer to the non local variable even when the function is out of the scope of the variables.