Tuesday, 30 March 2010

Bubble sort in a Mathematica pattern

The Mathematica programming language has many unusual characteristics, two of which are:

  • Everything is an expression.
  • Pattern-based rewrite rules are obscenely powerful.

These kinds of characteristics are the foundation of what makes Mathematica a powerful programming language. For example, the bubble sort algorithm can be implemented in a single line without a loop in Mathematica using a single conditional rewrite rule that exchanges adjacent elements when they are out of order:

bubble[xs___, x_, y_, ys___] := bubble[xs, y, x, ys] /; x > y

This definition causes a new rewrite rule to be injected into Mathematica's global table of rewrite rules. Mathematica then applies this rule to any subexpression it sees that has the form bubble[..]. The pattern on the left side of the rule searches for a pair of adjacent arguments (x and y) to bubble where x>y. If the pattern matches then the expression is rewritten such that x and y are exchanged.

This example not only demonstrates the remarkable expressiveness of the Mathematica programming language but also some of the ensuing problems. We have no idea how efficiently Mathematica's pattern matcher will find adjacent elements that are out of order and it is unlikely that Mathematica will optimize this down to an in-place swap. Consequently, we cannot begin to predict how much time or space this function will require. A quick benchmark shows that sorting 100 small integers this way takes a whopping 0.63 seconds!

No comments: