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.