THE TROUBLED PROGRAMMER

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, but 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()
    , smaller = []
    , 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!