Introduction
For last few years functional programming is trying to conquer imperative world. The monad keyword has become more and more popular. This was the reason I also joined to bounty hunters. I just wanted to nail the state monad. What's its origin? How could I derive it? I decided to try it in javascript. There are two reasons. The first one, javascript is the simplest, most popular and good enough functional language (Yes I know there are people who take it as a hoax :) ). The second, javascript hasn't got any special support for algebraic data structures. It is worth to mention also Mike Stay's youtube lectures about theory of category and Santosh Rajan's blog about functional programming in javascript, but what was missing to me, is the problem statement. The code is written as jasmine tests.
So let's try to find state monad.
The code - from zero to hero
The base problem can be expressed as follows:
it('dirty functions case', function () {
var increase = function (value) {
console.log('increasing ' + value);
return value + 1;
};
expect(increase(1)).toEqual(2);
});
The problem with it is that function signature doesn't reflect the fact of interaction with console.log object. It can be done in really simple way. Just add new argument 'log' to function arguments list. Or use currying to bind value and log as it is shown below:
it('first solution', function () {
var increase = function (value, log) {
log.push('increasing ' + value);
return value + 1;
};
var log = [];
var actual = increase(1, log);
expect(actual).toBe(2);
expect(log).toEqual(['increasing 1']);
var curryIncrease = function (value) {
return function (log) {
log.push('increasing ' + value);
return value + 1;
}
};
log = [];
expect(curryIncrease(2)(log)).toBe(3);
expect(log).toEqual(['increasing 2']);
});
Great. But now let think about situation when we want to combine two function like square(increase(2))(log), Our functions will be defined as follows:
it('two functions with values and states', function () {
var increase = function (value) {
return function (log) {
log.push('increasing ' + value);
return value + 1;
};
};
var square = function (f) {
return function (log) {
var value = f(log);
log.push('squaring ' + value);
return value * value;
}
};
var log = [];
var actual = square(increase(2))(log);
expect(actual).toBe(9);
expect(log).toEqual(['increasing 2', 'squaring 3'])
});
because 'increase' function returns function with signature log -> value, thus 'f' taken by 'square' is a function with signature log -> value. But now let think how to revert calls. So we want to call increase(square(2))(log) as well. This is my proposal:
it('now square and then increase', function () {
var increase = function (f) {
return function (log) {
var value = f(log);
log.push('increasing ' + value);
return value + 1;
};
};
var square = function (f) {
return function (log) {
var value = f(log);
log.push('squaring ' + value);
return value * value;
}
};
var lift = function (value) {
return function (log) {
return value;
}
};
var log = [];
var actual = increase(square(lift(2)))(log);
expect(actual).toBe(5);
expect(log).toEqual(['squaring 2', 'increasing 4']);
log = [];
actual = square(increase(lift(2)))(log);
expect(actual).toBe(9);
expect(log).toEqual(['increasing 2', 'squaring 3'])
});
Now both 'square' and 'increase' are really similar (nice fact!) and get 'f' as an argument thus we can call square(increase(...)) as well as increase(square(...)). It also means that we need the 'lift' function which lifts (converts) simple value to function which takes 'log' and returns 'value'.
When we look at state monad we notice that it handle on tuple (state, value). Why don't we see anywhere above? The answer is quite obvious. Our 'log' is mutable so let make it immutable then implementation of square and increase will turn to:
it('what in case when the log is immutable?', function () {
var increase = function (f) {
return function (log) {
var valueState = f(log);
return [valueState[0] + 1, immutablePush(valueState[1], 'increasing ' + valueState[0])];
};
};
var square = function (f) {
return function (log) {
var valueState = f(log);
return [valueState[0] * valueState[0], immutablePush(valueState[1], 'squaring ' + valueState[0])];
}
};
var lift = function (value) {
return function (log) {
return [value, log];
}
};
var actual = increase(square(lift(2)))([]);
expect(actual).toEqual([5, ['squaring 2', 'increasing 4']]);
actual = square(increase(lift(2)))([]);
expect(actual).toEqual([9, ['increasing 2', 'squaring 3']]);
});
The immutablePush is just a function which produces new array for log. Just to be strict let me show its implementation:
var immutablePush = function (array, log) {
var newArray = [];
newArray.push.apply(newArray, array);
newArray.push(log);
return newArray;
};
Now we return tuple (value, log) (yes, I exchanged positions of state and value intentionally to show that it doesn't matter anyway).
We are in functional world so we can expect that our functions are referentially transparent. It means that whatever is the number of invocations we expect that for the same arguments we get the same result. Let check if it applies to written code:
it('just check for referential transparency', function () {
var increase = function (f) {
return function (log) {
return [f(log)[0] + 1, immutablePush(f(log)[1], 'increasing ' + f(log)[0])];
};
};
var square = function (f) {
return function (log) {
return [f(log)[0] * f(log)[0], immutablePush(f(log)[1], 'squaring ' + f(log)[0])];
}
};
var lift = function (value) {
return function (log) {
return [value, log];
}
};
var actual = increase(square(lift(2)))([]);
expect(actual).toEqual([5, ['squaring 2', 'increasing 4']]);
actual = square(increase(lift(2)))([]);
expect(actual).toEqual([9, ['increasing 2', 'squaring 3']]);
});
So we see that whenever the 'f(log)' is called it returns same result.
Ok, now let ponder on situation when we want to write our invocation chain in slightly nicer way. So instead of square(increase(lift(2))([]) we want to have some mysterious object with 'invoke' method. The call would look something like: mysterious(lift(2)).invoke(increase).invoke(square)([]). What are then 'mysterious' and its 'invoke'? Answer below:
it('let compound functions', function () {
var lift = function (value) {
return function (log) {
return [value, log];
}
};
var mysterious = function (f ) {
this.f = f;
this.invoke = function (g ) {
return new mysterious(function (log) {
return g(f(log)[0])(f(log)[1]);
});
}
};
var square = function (value) {
return function (log) {
return [value * value, immutablePush(log, 'squaring ' + value)];
};
};
var increase = function (value) {
return function (log) {
return [value + 1, immutablePush(log, 'increasing ' + value)];
};
};
var m = new mysterious(lift(2));
expect(m.invoke(square).invoke(increase).invoke(square).f([])).toEqual([25, ['squaring 2', 'increasing 4', 'squaring 5']]);
});
Look how beautiful are increase and square functions! And note that 'g' function taken as an argument of invoke is a function which takes value and returns function which takes log and returns [value, log]. The signature can be expressed as value -> (log -> [value, log]).
When we look closer at 'g' we notice that it can be replaced by our 'mysterious' object! And the function returned by 'g' is just the mysterious' inner function 'f'! Let see how it looks in code.
it("probably I'm the monad", function () {
var lift = function (value) {
return function (log) {
return [value, log];
}
};
var mysterious = function (f ) {
this.f = f;
this.invoke = function (g ) {
return new mysterious(function (log) {
return g(f(log)[0]).f(f(log)[1]);
});
}
};
var square = function (value) {
return new mysterious(function (log) {
return [value * value, immutablePush(log, 'squaring ' + value)];
});
};
var increase = function (value) {
return new mysterious(function (log) {
return [value + 1, immutablePush(log, 'increasing ' + value)];
});
};
var m = new mysterious(lift(2));
expect(m.invoke(square).invoke(increase).invoke(square).f([])).toEqual([25, ['squaring 2', 'increasing 4', 'squaring 5']]);
});
When we look at Haskell 'bind' function definition or Scala 'flatMap' function definition we find that their signatures are exactly the same as our 'invoke'! We did monad but of course we have to prove it which will be done little later. Now let me add function 'map' which doesn't operate on log. This also allow to see in mysterious the functor!
it('functor, functions without the state', function () {
var lift = function (value) {
return function (log) {
return [value, log];
}
};
var mysterious = function (f ) {
this.f = f;
var me = this;
this.invoke = function (g ) {
return new mysterious(function (log) {
return g(me.f(log)[0]).f(me.f(log)[1]);
});
};
this.map = function (h ) {
var me = this;
return new mysterious(function (log) {
return [h(me.f(log)[0]), me.f(log)[1]];
});
}
};
var square = function (value) {
return value * value;
};
var increase = function (value) {
return new mysterious(function (log) {
return [value + 1, immutablePush(log, 'increasing ' + value)];
});
};
var m = new mysterious(lift(2));
expect(m.map(square).invoke(increase).map(square).f([])).toEqual([25, ['increasing 4']]);
});
We see that square is not operating on log in this case so it needs 'map' to be used in chain.
When we look at 'increase' we realize that we have to wrap the returned function into 'mysterious' object which is quite ugly. Instead of it let me define the function 'liftAndInvoke' which does it for us. The code of 'mysterious' will look like below.
it("I\'m the monad!", function () {
var lift = function (value) {
return function (log) {
return [value, log];
}
};
var mysterious = function (f ) {
this.f = f;
var me = this;
this.invoke = function (g ) {
return new mysterious(function (log) {
return g(me.f(log)[0]).f(me.f(log)[1]);
});
};
this.map = function (h ) {
var me = this;
return new mysterious(function (log) {
return [h(me.f(log)[0]), me.f(log)[1]];
});
};
this.liftAndInvoke = function (i ) {
return this.invoke(function (value) {
return new mysterious(i(value));
});
}
};
var square = function (value) {
return value * value;
};
var increase = function (value) {
return function (log) {
return [value + 1, immutablePush(log, 'increasing ' + value)];
};
};
var m = new mysterious(lift(4));
expect(m.map(square).liftAndInvoke(increase).map(square).f([])).toEqual([289, ['increasing 16']]);
});
Finally let me check if 'mysterious' meets the monad laws:
describe('monadic laws', function () {
var lift = function (value) {
return function (log) {
return [value, log];
}
};
var mysterious = function (f ) {
this.f = f;
var me = this;
this.invoke = function (g ) {
return new mysterious(function (log) {
return g(me.f(log)[0]).f(me.f(log)[1]);
});
};
this.map = function (h ) {
var me = this;
return new mysterious(function (log) {
return [h(me.f(log)[0]), me.f(log)[1]];
});
};
this.liftAndInvoke = function (i ) {
return this.invoke(function (value) {
return new mysterious(i(value));
});
}
};
it('1st monadic law: bind(unit(x), f) = f(x)', function () {
var tested = new mysterious(lift(3));
var f = function (value) {
return new mysterious(function (log) {
return [value + 2, 'test'];
});
};
expect(tested.invoke(f).f([])).toEqual(f(3).f([]));
});
it('2nd monadic law: bind(m, unit) = m', function () {
var tested = new mysterious(lift(3));
var unit = function (value) {
return new mysterious(lift(value));
};
expect(tested.invoke(unit).f([])).toEqual(tested.f([]));
});
it('3rd monadic law: bind(bind(m, f) g) = bind(m, x => bind(f(x), g))', function () {
var tested = new mysterious(lift(3));
var f = function (value) {
return new mysterious(function (log) {
return [value + 2, 'test f'];
});
};
var g = function (value) {
return new mysterious(function (log) {
return [value * value, 'test g'];
});
};
var arrow = function (f, g) {
return function (value) {
return f(value).invoke(g);
};
};
expect(tested.invoke(f).invoke(g).f([])).toEqual(tested.invoke(arrow(f, g)).f([]));
})
});
As the excercise you can validate 'mysterious' against the functor's laws :)!
