Implementation of a State monad in JavaScript

state-example-game.js

/*
 * 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

/*
 * 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

/*
 * 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

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

/*
 * 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

<!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

/*
 * 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.

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!

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