public
Last active

Implementation of a State monad in JavaScript

  • Download Gist
state-example-game.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
/*
* Example of a state monad in use. This is adapted from an example on
* the Haskell Wiki:
* http://www.haskell.org/haskellwiki/State_Monad#Complete_and_Concrete_Example_1
*/
require(['state', 'qunit'], function(state, qunit) {
 
/*
* playGame() is a recursive function that given an array of moves
* defines an algorithm for constructing a final game score. Along
* the way it creates a new game state for each move.
*
* The function does not actually execute that algorithm when it is
* invoked - it returns a state monad value instead. When that
* value is given a starting state then it executes.
*/
function playGame(moves) {
if (moves.length === 0) {
return state.get().bind(function(s) {
/*
* pure() sets a result value. This is the base case;
* so the value set here will be the final result of the
* algorithm.
*/
return state.pure(s.score);
});
}
 
var move = moves[0];
var rest = moves.slice(1);
 
/*
* Returns an "action" constructed by state.get(). The action
* retrieves the current state and assigns it as the monad's
* result value. The bind() call returns a modified action that
* can have different behaviors depending on the current
* value/state.
*/
return state.get().bind(function(s) {
var on = s.on;
var score = s.score;
var next;
switch(move) {
case 'a': next = state.put({ on: on, score: score + 1 }); break;
case 'b': next = state.put({ on: on, score: score - 1 }); break;
case 'c': next = state.put({ on: !on, score: score }); break;
default: next = state.put(s); // ignores unknown moves
}
 
/*
* The state.put() "action" replaces the current state with
* the given argument, which will be available in the next
* step of the algorithm. Note that state.put() does not
* perform any side effects; so simply calling state.put()
* does not have any effect. It is necessary to return the
* "action" to hook it in as the next step in the pipeline.
*/
return next.bind(function(_) {
/*
* Once the new state is installed, make a recursive
* call to operate on the next move in the list.
*/
return playGame(rest);
});
});
}
 
var initState = { on: false, score: 0 };
var moves = ['a','b','c','a','a','a','c','b','b','c','a','b','b','a','b'];
 
/*
* Creates a monad value for the given array of moves. Again this
* does not run the algorithm yet. It merely creates an "action"
* that is a composition of the simpler actions created in
* playGame().
*/
var game = playGame(moves);
 
qunit.test('produces the final score for a array of moves', 1, function() {
/*
* The evalState() method provides an initial state for the
* playGame algorithm. This is the point where, finally, the
* algorithm actually runs. The value of this expression is the
* final result value of the algorithm.
*/
var finalScore = game.evalState(initState);
qunit.equal(0, finalScore);
});
 
qunit.test('produces "on" state after given sequence of moves', 1, function() {
var finalOnState = game.execState(initState).on;
qunit.equal(true, finalOnState);
});
 
});
state-example.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
/*
* A contrived example of the State monad in action. If for some reason
* you don't want to use Array#reduce(), this is another way to go :)
*/
require(['state', 'qunit'], function(state, qunit) {
 
/*
* This function produces a pipeline of operations for a given
* array. Once seeded with an initial state, the pipeline will
* execute to produce a result value and a final state.
*/
function fooCounter(array) {
if (array.length === 0) {
return state.get().bind(function(counts) {
/*
* pure() sets a result value. At this point
* computation is complete.
*/
return state.pure(counts['foo']);
});
}
 
var head = array[0];
var tail = array.slice(1);
 
/*
* The function returns "actions" that make up the stateful
* algorithm. get() grabs the current value of the carried
* state. A callback is provided with instructions on how to
* proceed when that state is available.
*/
return state.get().bind(function(counts) {
/*
* This bit is impure. If I created a new object with the
* updated count instead of modifying the existing object
* then this program would be fully immutable.
*/
var count = counts[head] || 0;
counts[head] = count + 1;
 
/*
* Stores the updated state and proceeds to the next array
* element with the new state.
*/
return state.put(counts).bind(function(_) {
return fooCounter(tail);
});
});
}
 
/*
* This is the function that a consumer will actually call. It
* builds a State pipeline, seeds it with an initial value, and
* takes the result.
*/
function getFooCount(array) {
return fooCounter(array).evalState({});
}
 
qunit.test('counts number of "foo" instances in a list', 1, function() {
var count = getFooCount(['foo', 'foo', 'foo', 'bar', 'foo']);
qunit.equal(4, count);
});
 
});
state.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
/*
* Working with pure functions and avoiding mutable state can help to
* produce robust code. But if you want to avoid updating a shared
* variable, passing state from function to function explicitly can get
* ugly. The State monad addresses this: it makes program state
* available without explicit passing, while maintaining functional
* purity.
*/
define('state', function() {
 
function State(s) {
this.runState = s;
}
 
State.prototype = {
map: function(f) {
var runState = this.runState;
return new State(function(state) {
var prev = runState(state);
return { value: f(prev.value), state: prev.state };
});
},
 
join: function() {
var runState = this.runState;
return new State(function(state) {
var prev = runState(state);
var inner = prev.value.runState(prev.state);
return inner;
});
},
 
bind: function(f) {
return this.map(f).join();
},
 
evalState: function(initState) {
var result = this.runState(initState);
return result.value;
},
 
execState: function(initState) {
var result = this.runState(initState);
return result.state;
}
};
 
function get() {
return new State(function(state) {
return { value: state, state: state };
});
}
 
function put(newState) {
return new State(function(state) {
return { value: undefined, state: newState };
});
}
 
function modify(f) {
return get().bind(function(state) {
var newState = f(state);
return put(newState);
});
}
 
function gets(f) {
return get().bind(function(state) {
var valFromState = f(state);
return pure(valFromState);
});
}
 
function pure(v) {
return new State(function(state) {
return { value: v, state: state };
});
}
 
return {
get: get,
put: put,
modify: modify,
gets: gets,
pure: pure
};
 
});
stateT-async-example.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
require([
'stateT', 'monadicPromise', 'jquery', 'qunit'
], function(stateT, mpromise, $, qunit) {
 
/*
* Layers stateT on top of monadicPromise to create a new monad that
* has the properties of both.
*/
var state = stateT(mpromise);
 
function plusOneTracker() {
return state.lift(getPlusOne()).bind(function(contentId) {
return state.get().bind(function(counts) {
var count = counts[contentId] || 0;
var updatedCounts = insert(contentId, count + 1, counts);
 
return state.put(updatedCounts).bind(function(_) {
return state.lift(showPlusOnes(contentId, count + 1)).bind(function(_) {
return plusOneTracker();
});
});
 
});
});
}
 
function trackPlusOnes() {
plusOneTracker().execStateT({});
}
 
function getPlusOne() {
return getEvent('click', '.plus-one').map(function(link, event) {
event.preventDefault();
var contentId = $(link).data('contentId');
return contentId;
});
}
 
function showPlusOnes(contentId, count) {
$('.plus-one[data-content-id="'+ contentId +'"]').text(count);
return mpromise.fromDeferred($.Deferred(function(deferred) {
deferred.resolve();
}).promise());
}
 
qunit.asyncTest('updates a plus-one counter', 4, function() {
trackPlusOnes();
 
var $link = $('<a href="#" class="plus-one" data-content-id="4">0</a>');
$link.appendTo('body');
 
qunit.equal('0', $link.text());
$link.trigger('click');
 
setTimeout(function() {
qunit.equal('1', $link.text());
$link.trigger('click');
 
setTimeout(function() {
qunit.equal('2', $link.text());
$link.trigger('click');
 
setTimeout(function() {
qunit.equal('3', $link.text());
$link.remove();
qunit.start();
}, 100);
}, 100);
}, 100);
});
 
/** Helper to create a monadic event system **/
 
function getEvent(eventType, selector) {
var deferred = $.Deferred();
 
$(document).one(eventType, selector, function(event) {
deferred.resolve(this, event);
});
 
return mpromise.fromDeferred(deferred.promise());
}
 
function insert(k, v, map) {
var newMap = $.extend({}, map);
newMap[k] = v;
return newMap;
}
 
});
 
 
/*
* Defines a new promise API that corresponds to the interface that
* stateT expects. The implementation just wraps jQuery Deferred.
*/
define('monadicPromise', ['jquery'], function($) {
 
function fromDeferred(promise) {
function map(f) {
var p = promise.pipe(function(/* v */) {
var result = f.apply(null, arguments);
return result.origPromise ? result.origPromise : result;
});
return fromDeferred(p);
}
 
var bind = map;
 
function join() {
return promise.bind(function(p) {
return p;
});
}
 
return {
map: map,
bind: bind,
join: join,
origPromise: promise
};
}
 
function pure(v) {
return fromDeferred($.Deferred(function(deferred) {
deferred.resolve(v);
}).promise());
}
 
return {
pure: pure,
fromDeferred: fromDeferred
};
 
});
stateT.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
/*
* StateT is a monad transformer, meaning that it stacks the behavior of
* the State monad onto another monad type.
*/
define('stateT', function() {
 
return function(innerMonad) {
 
function StateT(s) {
this.runStateT = s;
}
 
StateT.prototype = {
map: function(f) {
var runStateT = this.runStateT;
return new StateT(function(state) {
var m = runStateT(state);
return m.map(function(s) {
return { value: f(s.value), state: s.state };
});
});
},
 
bind: function(f) {
var runStateT = this.runStateT;
return new StateT(function(state) {
var m = runStateT(state);
return m.bind(function(s) {
return f(s.value).runStateT(s.state);
});
});
},
 
join: function() {
return this.bind(function(s) {
return s;
});
},
 
evalStateT: function(initState) {
var m = this.runStateT(initState);
return m.bind(function(result) {
return innerMonad.pure(result.value);
});
},
 
execStateT: function(initState) {
var m = this.runStateT(initState);
return m.bind(function(result) {
return innerMonad.pure(result.state);
});
}
};
 
function pure(v) {
return new StateT(function(state) {
return innerMonad.pure({ value: v, state: state });
});
}
 
function lift(m) {
return new StateT(function(state) {
return m.bind(function(v) {
return innerMonad.pure({ value: v, state: state });
});
});
}
 
function get() {
return new StateT(function(state) {
return innerMonad.pure({ value: state, state: state });
});
}
 
function put(newState) {
return new StateT(function(state) {
return innerMonad.pure({ value: undefined, state: newState });
});
}
 
function modify(f) {
return get().bind(function(state) {
var newState = f(state);
return put(newState);
});
}
 
function gets(f) {
return get().bind(function(state) {
var valFromState = f(state);
return pure(valFromState);
});
}
 
return {
pure: pure,
lift: lift,
get: get,
put: put,
modify: modify,
gets: gets
};
 
};
 
});
tests.html
HTML
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>State monad tests</title>
<link rel="stylesheet" href="http://code.jquery.com/qunit/qunit-1.10.0.css" />
</head>
<body>
<div id="qunit"></div>
<script src="https://raw.github.com/jivesoftware/tAMD/master/define.js"></script>
<script>
define.amd.jQuery = true;
</script>
<script src="http://code.jquery.com/jquery-1.8.2.min.js"></script>
<script src="http://code.jquery.com/qunit/qunit-1.10.0.js"></script>
<script>
define('qunit', function() {
return {
module: module,
test: test,
asyncTest: asyncTest,
stop: stop,
start: start,
ok: ok,
equal: equal
};
});
</script>
<script src="state.js"></script>
<script src="state-example-game.js"></script>
<script src="state-example.js"></script>
<script src="tests.js"></script>
<script src="stateT.js"></script>
<script src="stateT-async-example.js"></script>
</body>
</html>
tests.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
/*
* All instances of the Monad typeclass should obey the three monad laws:
*
* Left identity: return a >>= f ≡ f a
* Right identity: m >>= return ≡ m
* Associativity: (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)
*/
 
require(['state', 'qunit'], function(state, qunit) {
 
function randVal() {
return Math.floor(Math.random() * 1000 - 500);
}
 
var a = randVal();
var b = randVal();
var c = randVal();
 
function f (x) {
return state.pure(x + b);
}
 
function g (x) {
return state.pure(x + c);
}
 
var m = state.pure(a);
 
qunit.test('left identity', 1, function() {
qunit.equal(
state.pure(a).bind(f).evalState(),
f(a).evalState()
);
});
 
qunit.test('right identity', 1, function() {
qunit.equal(
m.bind(state.pure).evalState(),
m.evalState()
);
});
 
qunit.test('associativity', 1, function() {
qunit.equal(
m.bind(f).bind(g).evalState(),
m.bind(function(x) { return f(x).bind(g); }).evalState()
);
});
 
});

So this is good for synchronous code. But since this is JavaScript a pattern will not be very useful unless it can accommodate async code. It should be possible to put a State layer on top of RxJS or a similar library to accomplish that.

TODO: Write async implementation and examples.

Async implementation and example added.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.