Making is thinking.


Fascinated by the use of recursion and pattern matching in Erlang, I marvel at a quicksort implementation.

IN THE PROCESS of learning Erlang I find myself mesmerized by particularly concise—yet rich—pieces of code which make me pause to contemplate:

quicksort([]) -> [];
quicksort([Pivot|Rest]) ->
  quicksort([Smaller || Smaller <- Rest, Smaller =< Pivot])
  ++ [Pivot] ++
  quicksort([Larger || Larger <- Rest, Larger > Pivot]).

This naive, easy to understand, quicksort takes the first item of a list as a pivot by which it sorts the items in two lists; one for smaller, the other for larger items.

Trying to express similar in JavaScript, I wrote:

function quicksort (a) {
  if (a.length <= 1) return a
  var pivot = a.shift()
  var smaller = []
  var larger = []
  a.forEach(function (x) {
    x <= pivot ? smaller.push(x) : larger.push(x)
  return quicksort(smaller).concat(pivot, quicksort(larger))

In his highly recommended book Learn You Some Erlang for Great Good!, from where the above quicksort stems, Fred Hébert writes:

Recursion coupled with pattern matching is sometimes an optimal solution to the problem of writing concise algorithms that are easy to understand. By subdividing each part of a problem into separate functions until they can no longer be simplified, the algorithm becomes nothing but assembling a bunch of correct answers coming from short routines.

Contemplate—for Great Good!