Haskell Quicksort in JavaScript

Haskell has a particularly elegant implementation of the quicksort algorithm:

qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (x:xs) =
  let smaller = qs [a | a <- xs, a <= x]
      bigger = qs [a | a <- xs, a > x]
  in  smaller ++ [x] ++ bigger

This algorithm creates a new array that is sorted instead of sorting the given array in place. Therefore, there is no point in implementing a partitioning strategy (usually Hoare's).

To someone who is unfamiliar with Haskell, this may look like a bunch of nonsense. Let's break it down and see how we might come up with an elegant version in JavaScript.

Type Signature

qs :: (Ord a) => [a] -> [a]

This is just a type signature which can be read like this: "qs is a function that takes an array of as and produces a new array of as where each element a can be compared to another." The (Ord a) part is a type constraint that means that as need to be comparable, which makes sense since this is a sorting algorithm.

Pattern Matching

qs [] = []
qs (x:xs) = -- and so on...

Pattern matching is kind of like function overloading combined with destructuring. JavaScript does not have function overloading, but it does have destructuring. We can write (x:xs) as [x, ...xs] in JavaScript. Unfortunately, we'll have to manually check if the array is empty or not.

Let Expression

let smaller = qs [a | a <- xs, a <= x]
    bigger = qs [a | a <- xs, a > x]
in  smaller ++ [x] ++ bigger

In Haskell, everything is an expression instead of a statement. Expressions are things that produce values. Statements are just lines of code that do something. Sometimes, it is useful to define intermediate values in an expression, and that is what the let block does. The result of the block is an array of smaller ++ [x] ++ bigger.

List Comprehension

[a | a <- xs, a <= x]

List comprehension generates lists (or arrays) using generators and guards (or filters). This code can be read "give me a list of as where each a is taken from the xs list and is less than or equal to x." (This is really just syntactic sugar on top of do notation, which itself is just syntactic sugar for monadic composition, but that's a topic for another time.)

Unfortunately, JavaScript does not have list comprehension, so the best we can do is use the Array.filter method: xs.filter(s => s <= x). Arrow functions enable a relatively elegant alternative.

Now in JavaScript

Here's the cool trick to put everything together: since there are only two branches of logic, the ternary operator provides a great mechanism for handling the conditions. We can use destructuring to split the array to its head and tail. Then we use the ternary operator to return an empty array if the head is undefined (since the array was empty), or the new array made up of the smaller array, current element, and bigger array. Here is the final code:

const qs = ([x, ...xs]) => x === undefined 
  ? [] 
  : [
    ...qs(xs.filter(s => s <= x)),
    x,
    ...qs(xs.filter(b => b > x))
  ]

The coolest part of this implementation is that the whole thing is just an expression! There are no variable declarations at all (except the quicksort algorithm itself being assigned to a constant).

This is definitely not the most efficient implementation of the quicksort algorithm, but it demonstrates how to write elegant code that makes use of the features of JavaScript. It would be cool to have pattern matching, list comprehensions, and let expressions in JavaScript, but you can get pretty far with the tools that JavaScript already provides. In an industry where code clarity and maintainability is becoming increasingly more critical and where device capacity is practically overkill, the ability to write correct, clear and concise code is invaluable.

Edit:

Amn3s1a2018 pointed out that my original code did not explicitly check for x === undefined and would therefore fail for arrays including zeros.

Amn3s1a2018 • Oct 21 '21

It's a cool refactor example, and its an example for a common error ...
The ternary operator nice replacement for the overload, but the correct way would

surprise, surprise

x !== undefined ? etc.

'cause this way qs filters out all falshy element from the array and drops there tail too.

As already noted, this isn't the most efficient way of sorting in JavaScript, and I would not recommend actually using it in production. If you want an efficient algorithm for sorting that gives you a new array, use this:

const qs = (arr) => [...arr].sort((a, b) => a - b);