## Thursday, July 25, 2013

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 ]
``````

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 [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 [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
}

return [v]
}
``````

and rewrite `forEach2d`

``````function forEach2d(array1, array2, callback) {
})
})
}
``````

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`.

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)
}

return v
}
``````

It is not a very useful monad. But it is a valid 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)
}

return v
}
``````

``````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]
}
mf(x)                                  ==>>  [ 8 ]
``````

``````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 ]
``````

``````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]
}
})                                         ==>>  [ 6, 12, 18 ]
``````

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 wrap(curriedCb, index) {
return function mf(v) {
return (index === values.length - 1) ?
monad(values[index + 1], wrap(curriedCb(v), index + 1))
}
}
}
return x + y
})                           //==>> [ 4, 5, 5, 6 ]
``````

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

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()
}

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!

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];
}
}
``````

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])
}
}
}

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
}
}
``````

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)
})
}
}
return function(continuation) {
return continuation(value)
}
}
``````

1. Excellent post. I read a lot of monads, but still these things escaped may understanding and how to create them in practice to solve which problems. But now I think I've got it. Thanks.

2. I am a bit confused. Wikipedia says that a monadic function is any function with arity 1 http://en.wikipedia.org/wiki/Arity