Simple recursive pattern matching in Javascript

match.js

// Simple recursive pattern matching
// =================================
//
// The provided `match` function matches recursively against
// javascript values, and returns a set of bindings made against
// the source.
//
// in these examples `match._` is aliased as `_`. 
//
// `match(_, data)` succeeds
// `match(_(key), data)` succeeds and binds `data` as `key`, if no binding exists for `key` or
// the binding for `key` matches `data` 
// `match([pat, ...], [data, ...])` succeeds if each `match(pat, data)` succeeds
// `match({key: pat, ...}, { key: data, ...})` succeeds if `match(pat, data)` succeeds 
//  otherwise `match(pat, data)` succeeds if `pat == data`
//
// `match( [ _('a'), _('b') ], [1 , 2] )` succeeds, returning these bindings `{ a: 1, b: 2}`.
// `match( [ _('a'), 3 ], [1 , 2] )` fails, returning `null`
// `match( [ _('a'), _('a') ], [1 , 1] )` succeeds, returning `{ a: 1 }`
// `match( [ _('a'), _('a') ], [1 , 2] )` fails, returning `null`
// `match( [ 1, 2 ], [1 , 2] )` succeeds, returning `{}`
var match;
(function () {
    var _match, Symbol, bind, type, assert, _,

        hasOwn = {}.hasOwnProperty,
        toString = {}.toString;

    match = function (pattern, value) {
        return _match(pattern, value, {});
    };

    _ = match._ = function (str) {
        return new Symbol(str);
    };

    _match = function (pattern, value, matches) {
        if (matches == null) return null;

        var i;

        switch (type(pattern)) {
            case 'wildcard':
                return matches;

            case 'symbol':
                return bind(pattern, value, matches);

            case 'array':
                i = pattern.length;

                while (i--) {
                    matches = _match(pattern[i], value[i], matches);
                }

                return matches;

            case 'object':
                for (i in pattern) if (hasOwn.call(pattern, i)) {
                    matches = _match(pattern[i], value[i], matches);
                }

                return matches;

            default:
                return pattern == value ? matches : null;
        }
    };

    type = function (val) {
        // The internal property [[Class]] of a given javascript
        // object is a reliable way to identify various builtins
        //
        // ECMA-262 8.6.2 discusses the internal properties
        // common to all Ecmascript Objects including [[Class]]
        //
        // ECMA-262 15.2.4.2 discusses the use of
        // Object.prototype.toString to observe [[Class]]

        return val == null ? String(val)
            :  val === _ ? 'wildcard'
            :  val instanceof Symbol ? 'symbol'
            :  toString.call(val).slice(8, -1).toLowerCase();
    };

    Symbol = function (str) {
        this.value = str;
    };

    bind = function (sym, value, matches) {
        var key = sym.value;

        if (!matches.hasOwnProperty(key)) {
            matches[key] = value;
            return matches;
        } else {
            return _match(matches[key], value, matches); 
        }
    };

    if (typeof require == 'function' &&
        (assert = require('assert'))) {

        var A = _('a'), B = _('b'), C = _('c'), D = _('d');

        assert.deepEqual(match(A, 5),
                        {a: 5});

        assert.deepEqual(match([ A ],
                               [ 5 ]),
                        {a: 5});

        assert.deepEqual(match([ A, 6 ],
                               [ 5 ]),

                        null);

        assert.deepEqual(match([ A, A ],
                               [ 5, 6 ]),

                         null);

        assert.deepEqual(match([ A, A ],
                               [ 5, 5 ]),

                         {a: 5});

        assert.deepEqual(match([ _, A ],
                               [ 5, 5 ]),

                         {a: 5});

        assert.deepEqual(match([[A, [B]], C, D],
                               [[1, [2]], 3, 4]),

                         {a: 1, b: 2, c: 3, d: 4});

        assert.deepEqual(match({foo: A, bar: B },
                               {foo: 1, bar: 2}),

                         {a: 1, b: 2});

        assert.deepEqual(match({foo: [A, 3], bar: B },
                               {foo: [1, 3], bar: 2}),

                         {a: 1, b: 2});
    }
}());