Create a gist now

Instantly share code, notes, and snippets.

Implementation of a State monad in JavaScript
/*
* 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);
});
});
/*
* 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);
});
});
/*
* 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
};
});
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 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
};
};
});
<!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>
/*
* 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()
);
});
});
@hallettj
Owner
hallettj commented Nov 9, 2012

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.

@hallettj
Owner

Async implementation and example added.

@weidagang

This code is well documented, but it would be even better if there's type hint for the parameters and return value for the functions. For instance, when I see function playGame(moves) { ... }, I'd like to know it's input type and output type from the comments. Thanks!

@C4Phone
C4Phone commented May 11, 2016

[shamelessplug] Hi everyone. there is a newer implementation using Lambdas and TypeScript. Please refer to the "test.ts" in this gist [\shamelessplug]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment