Advanced Pattern Matching in JavaScript

We’ll start with the pat­tern matcher we built in the pre­vi­ous ar­ti­cle . If you haven’t read that yet, I would sug­gest you do so be­cause it will be the foun­da­tion for this one. Re­call the fi­nal fac­to­r­ial func­tion:

var fact = match(
  [0, function() { return 1; }],
  [$('n'), function(result) {
    return result.n * fact(result.n - 1);
   }]
);

It would be nice if we could ad­dress each vari­able by its name in both the pat­tern and clo­sure. Un­for­tu­nately, there is no way in JavaScript to fig­ure out the name of a vari­able, so we can not write some­thing like this:

var fact = match(
  [0, function()  { return 1; }],
  [n, function(n) { return n * fact(n - 1); }]
);

We can how­ever ap­proach a sim­i­lar syn­tax if we give up named vari­ables and go for the or­der in which they are spec­i­fied. This is sim­i­lar to how pre­pared SQL statements work in most pro­gram­ming lan­guages. In­stead of call­ing them vari­ables we’ll call them pa­ra­me­ters from now on. For sim­plic­i­ty’s sake we use a magic num­ber as our pa­ra­me­ter.

Be­fore pass­ing the pat­tern ex­pres­sion to the unify method we rewrite it us­ing the visit_pattern method also in the JU­nify li­brary. On each rewrite we cre­ate in­creas­ingly num­bered vari­ables when we en­counter a pa­ra­me­ter. The rewrit­ing step is lo­cated in the outer clo­sure so it is only done once per pat­tern. When the unify method re­turns we it­er­ate through the re­sult ob­ject and cre­ate an ar­ray, which we pass to the clo­sure func­tion.

In the code be­low, the match func­tion is re­named to the more func­tional name fun, since we’re not re­ally match­ing any­more but definin­ing new func­tions. The mod­ule is also changed so that it throws an ex­cep­tion if none of the pat­terns match in­stead of re­turn­ing un­de­fined.

match_parameter = 0xABADBABE;

fun = function () {
  var unify     = unification.unify,
    visit_pattern = unification.visit_pattern,
    variable    = unification.variable,
    slice     = Array.prototype.slice;

  function rewrite(pattern, i) {
    var v = {
      'atom' : function (value) {
        var result;
        if (value === match_parameter) {
          result = variable(i);
          i += 1;
          return result;
        }
        else {
          return value;
        }
      },
      'func' : function (f) {
        var result = variable(i, f);
        i += 1;
        return result;
      }
    };
    return visit_pattern(pattern, v);
  }

  function fun_aux(patterns, value) {
    var i, result, length, key;
    var result_arguments = [];

    for (i = 0; i < patterns.length; i += 1) {
      length = patterns[i].length;

      result = unify(patterns[i].slice(0, length - 1), value);
      if (result) {
        // iterate through the results and insert them in
        // the correct location in our result array
        for (key in result) {
          if (result.hasOwnProperty(key)) {
            result_arguments[key] = result[key];
          }
        }
        // call the closure using the result array
        return patterns[i][length - 1].apply(
          null, result_arguments
        );
      }
    }
    throw {
      name: 'MatchError',
      message: 'Match is not exhaustive: (' + value + ')' +
           ' (' + patterns + ')'
    };
  }

  return function() {
    var patterns = slice.apply(arguments),
      i, l, c;

    for (i = 0; i < patterns.length; i += 1) {
      l = patterns[i].length;

      if (l >= 2 &&
        typeof patterns[i][l - 1] === 'function') {
        c = patterns[i][l - 1];
        patterns[i] = [].concat(
          rewrite(patterns[i].slice(0, l - 1), 0)
        );
        patterns[i].push(c);
      }
    }
    return function() {
      return fun_aux(patterns, slice.apply(arguments));
    };
  };
}();

If we rewrite the fac­to­r­ial func­tion us­ing the new syn­tax the end re­sult should look like this:

var $ = match_parameter;

var fact = fun(
  [0, function()  { return 1; } ],
  [$, function(n) { return n * fact(n - 1); } ]
);

The syn­tax could be im­proved fur­ther by us­ing JavaScript 1.8 which al­lows a short-hand clo­sure syn­tax. Un­for­tu­nately at the time of writ­ing JavaScript 1.8 is only sup­ported by Fire­fox 3. This ex­am­ple shows what pat­tern match­ing could look like in JavaScript 1.8.

var $ = match_parameter;

var fact = fun(
  [0, function()  1],
  [$, function(n) n * fact(n - 1)]
);

Algebraic data types

Pat­tern match­ing can also be used with Sjo­erd Viss­cher’s Al­ge­braic data type li­brary. You can read more about al­ge­braic data types on Wikipedia if you’re not fa­mil­iar with them. In the fol­low­ing ex­am­ple we de­fine a sim­ple bi­nary tree data type. The tree can con­tain ei­ther Void or a Bt tu­ple. The tu­ple con­sists of a value, and two branches called left and right. In the ML pro­gram­ming lan­guage we would de­fine a poly­mor­phic bi­nary tree like this:

datatype 'a binarytree = Void | Bt of 'a * 'a binarytree * 'a binarytree

In JavaScript — us­ing the ADT li­brary — it looks like this (note that this bi­nary tree is not poly­mor­phic, its val­ues are Num­bers.) All the code ex­am­ples from now are writ­ten in JavaScript 1.8 be­cause the ADT li­brary uses that as well. How­ever, apart from the slightly more ver­bose syn­tax, there’s noth­ing that would­n’t work in other JavaScript ver­sions.

var BinaryTree = Data(function(binarytree) ({
  Void : {},
  Bt: {
    v: Number, L: binarytree, R: binarytree
  }
}));

We can then cre­ate a sim­ple bi­nary tree in­stance us­ing this de­f­i­n­i­tion. A vi­sual rep­re­sen­ta­tion of this bi­nary tree is shown be­low. The code be­low also de­fines two short hand vari­ables for the match pa­ra­me­ter and the wild­card con­stant.

var bt = Bt(4,
       Bt(2, Bt(1,Void,Void),
           Bt(3,Void,Void)),
       Bt(8, Bt(6, Bt(5,Void,Void),
             Bt(7,Void,Void)),
           Bt(9,Void,Void)));

var $ = match_parameter;
var _ = unification._; // wildcard

We can now de­fine var­i­ous func­tions, for ex­am­ple to cal­cu­late the num­ber of leafs (nodes with­out chil­dren) in the tree, or a func­tion to test whether a value is a mem­ber of the bi­nary tree. It is pos­si­ble to use the data types in pat­terns, for ex­am­ple the numLeafs method first matches on an empty node, then a leaf node and fi­nally on any other kind of node. The isMember method shows that the match­ing is not lim­ited to one func­tion pa­ra­me­ter; the value to search for is taken as the first pa­ra­me­ter and the bi­nary tree as the sec­ond pa­ra­me­ter.

var numLeafs = fun(
  [Void, function() 0],        // empty node
  [Bt(_, Void, Void), function() 1], // leaf node
  [Bt(_, $, $), function(L, R) numLeafs(L) + numLeafs(R)]
);

var isMember = fun(
  [_, Void, function() false],
  [$, Bt($, $, $), function(x, v, L, R) x === v || (isMember(x, L) || isMember(x, R))]
);

numLeafs(bt);   // 5
isMember(10, bt); // false
isMember(3, bt);  // true

The fol­low­ing two func­tions re­turn a list of all the el­e­ments us­ing in or­der and pre or­der tra­ver­sals of the bi­nary tree.

var inorder = fun(
  [Void, function() []],
  [Bt($, $, $), function(v, L, R) inorder(L).concat([v], inorder(R))]
);

var preorder = fun(
   [Void, function() []],
   [Bt($, $, $), function(v, L, R) [v].concat(preorder(L), preorder(R))]
);

inorder(bt);    // [1,2,3,4,5,6,7,8,9]
preorder(bt);   // [4,2,1,3,8,6,5,7,9]

A real im­ple­men­ta­tion of a bi­nary tree would of course not use the data types and func­tions de­fined in this ar­ti­cle for per­for­mance rea­sons, but a bi­nary tree serves as a good in­tro­duc­tion to both pat­tern match­ing and al­ge­braic data types. You can down­load the source for this ar­ti­cle, it should run on any browser that sup­ports JavaScript 1.5 and up (though the ex­am­ples and the al­ge­braic data type li­brary re­quire ver­sion 1.8.)