DEV Community

Cover image for Haskell Quicksort in JavaScript
Caleb Weeks
Caleb Weeks

Posted on

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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...
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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))
  ]
Enter fullscreen mode Exit fullscreen mode

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.

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.

The updated version will still fail for arrays containing undefined, but sorting such an array would be difficult because you would have to decide what to do with undefined values (probably remove them). Actually, if the array does not have undefined as the first element, the filters will get rid of the rest of them and it will still work.

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);
Enter fullscreen mode Exit fullscreen mode

Discussion (24)

Collapse
qm3ster profile image
Mihail Malo

JS and current devices are slow enough.
Even methods like Array.filter should be used sparingly, since they eagerly allocate a new array on every single call.
Unfortunately, neither are iterators and generators optimized enough (yet?) in JS runtimes.

The Haskell definition is indeed elegant, but it just doesn't scale to JS, at least for the time being.

Collapse
weeksseth profile image
Caleb Weeks Author

I agree with your sentiment, and would not recommend actually using this code in production. It definitely won't be quick! JavaScript performance is less of a concern as it used to be. As for Array.filter, the tradeoff has to be made between saving machine performance (both speed and space), and human performance (clarity and maintainability).

Collapse
qm3ster profile image
Mihail Malo

I appreciate your readability concerns, but that article looks rather insane to me.
He starts by benchmarking absolutely bare, asm.js level code:

const ITERATIONS = 1000000000;

function main() {
    let myNum = 0;
    for (let i = 0; i <= ITERATIONS; i++) {
        myNum *= i;
        myNum++;
    }
}
Enter fullscreen mode Exit fullscreen mode

Actually, astonished that it didn't optimize to O(1)/constant time/noop in both languages, since the output is unobservable. Was the C compiled without optimization? 🤔

He then proceeds to rewrite

let smallest = Infinity;
const numbersLength = numbers.length; // avoid property look up in loop
for (let i = 0; i < numbersLength; i++) {
    const number = numbers[i]; // avoid repeated index lookups
    if (number > 0 && number < smallest)  smallest = number;
}
Enter fullscreen mode Exit fullscreen mode

again, asm.js spartanity code, but both of the things mentioned in the comments actually optimize well in JIT
into

numbers
  .filter(x => x > 0) // remove negative values
  .sort((a, b) => a-b)[0];
Enter fullscreen mode Exit fullscreen mode

instead of

numbers
  .filter(x => x > 0)
  .reduce((a, x) => x < a ? x : a)
Enter fullscreen mode Exit fullscreen mode

which in the future can be written as follows to avoid the intermediate array:

import {filter, reduce} from 'std:Iterable';
numbers
  |> filter(x => x > 0, %)
  |> reduce((a, x) => x < a ? x : a, %)
Enter fullscreen mode Exit fullscreen mode

introducing a whole ass mutable sorting step instead of a min reduce, fundamentally transforming the algorithm from O(n) to O(n log n), on TOP of the temporary memory allocation and slower constant factor.

Up next, he has delete user.password vs user.password = undefined.
Oh, it takes 1 billion iterations to show a difference between the two? Try benchmarking the whole application that contains this line. Look at memory use and battery power consumption.
How about the fact that the deletion affects the speed of all of your code that handles user-type objects by turning them from template objects into dynamic dictionaries or at best duplicating the monomorphised jitted code in memory, meaning less of it fits into the CPU cache?

Thread Thread
weeksseth profile image
Caleb Weeks Author

Would love to see a better real-world benchmark! If you can find codebase where overuse of Array.filter has resulted in an application that is unusable, I would love to see it!

Thread Thread
qm3ster profile image
Mihail Malo

And last but not least, see how competitive WASM is with JS, even when supposedly having to run through a JS glue layer, in JS's historical home of the browser.
And this is not about fancy ergonomic end-user-written business logic, this is about web frameworks, worked on for years to improve performance at any cost. You know they aren't using delete or forEach.
And yet just look at those memory allocation numbers.

How fast JS runtimes are, given the language specification, is a huge achievement and nothing short of a miracle. But when you regard JS as the delivery target, because that's what runs in all browsers, I don't think it's ever right to completely forget about how to write to make the best use of those efforts.

Thread Thread
qm3ster profile image
Mihail Malo

I'd love to see that too. I'd tongue-in-cheek say facebook.com, but that's rendered unusable (performance-wise) by quite a bit more than Array methods :)
(They are used there, and not transpiled, though, which I found rather surprising.)

Thread Thread
weeksseth profile image
Caleb Weeks Author

Haha, truthfully, I've been thinking the same thing about Facebook. There are times I can barely get it to fully render. I think their problem (and the problem with React in general) is that literally everything is replicated in the virtual DOM. I would love to see a JavaScript compiler to WebAssembly that turns things like Array.filter into faster solutions. Paired with a UI library that does virtual DOM in web workers, it could give us the best of both worlds (declarative code that compiles to optimized low level constructs).

Thread Thread
qm3ster profile image
Mihail Malo

I'm just assmad that Array.filter et al got added to the language specification, with all its awkwardness like creating an array, and passing so so many arguments to the callable passed. In addition to thwarting attempts at .reduce(Math.max) and .forEach(console.log), it causes arity mismatch which once again causes a miniscule deoptimization. Because, honestly, who writes .reduce((a, x, _, _) =>? Not many :v

Virtual DOM seems to be fundamentally too expensive for the performance people want, so a different model like reactive signals that bypasses it entirely is needed. I shitposted about it here yesterday.

Writing the business logic (including bringing in performant libraries that you use in the backend or native application) in the same language as the UI helpers and compiling it to WASM makes sense to me. The speed of WASM DOM modification is sure to increase somewhat in the future, but currently the critical performance downside for me is first-time startup performance. Sure, caching compiled modules is fast and efficient, but is shipping a raw HTML loading/landing/login page while the WASM downloads and compiles really enough?

Perhaps the situation will improve as people make sense of dynamically linking multiple pieces of WASM together, with the granularity and enthusiasm they show for JS bundle code splitting?

Collapse
darrylnoakes profile image
Darryl Noakes • Edited on

Just a question, I may be missing something.

You said

Then we use the ternary operator to return an empty array if the head is undefined.

Yet your code is:

x !== undefined 
  ? [] 
  : [
    ...
  ]
Enter fullscreen mode Exit fullscreen mode

This will return an empty array when x is not undefined, and do more sorting if it is undefined.

Indeed, I ran the following code, and it logged [].

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

let arr = [5, 3, 1, 8, 6, 0, 2, 4, 7, 9];

console.log(qs(arr));
Enter fullscreen mode Exit fullscreen mode

To fix, simply change the !== undefined to === undefined.
You could also swap the clauses in the ternary expression instead.

I tested this and it works.
That will filter out any undefineds, or return an empty array if the first element is undefined.
null gets sorted to the the beginning of the array.

Collapse
darrylnoakes profile image
Darryl Noakes • Edited on

Update:

I played around with it and came up with this:

let qs = (xs) => (
  xs.length > 0
    ? xs[0] !== undefined
      ? [
          ...qs(xs.slice(1).filter(s => s <= xs[0])),
          xs[0],
          ...qs(xs.slice(1).filter(b => b > xs[0]))
        ]
      : qs(xs.slice(1))
    : []
)
Enter fullscreen mode Exit fullscreen mode

This allows for having undefined at the beginning of the array. Not as elegant, but required due to x being undefined if an empty array is passed in (which is when the quicksort recursion ends and starts "undoing").

I did a few runs in JSBen.ch using my Pi 4 4GB.

  • orig: (23981) 100%
  • this: (15948) 66.5%
  • native: (14596) 60.86%

JSBen.ch test.

JSBench.me was less favorable.
I get this:

  • orig ~6000 - ~9500 ops/s; ~60% - ~85% slower
  • this: ~3000 - ~5000 ops/s; ~75% - ~95% slower
  • native: ~24000 ops/s

JSBench.me test

Collapse
sebastianfrey profile image
Sebastian Frey

Or use nested ternary operators:

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

let arr = [5, 3, 1, 8, 6, 0, 2, 4, 7, 9];

console.log(qs(arr));
Enter fullscreen mode Exit fullscreen mode
Thread Thread
darrylnoakes profile image
Darryl Noakes

I tried to figure out something like that, but got stuck.
Much better, thanks!

(Now to rerun the benchmarks...)

Thread Thread
darrylnoakes profile image
Darryl Noakes • Edited on

New benchmark results:

Run 1:

  • native (23740) 100%
  • orig quicksort (15751) 66.35%
  • undefined-safe quicksort (15673) 66.02%

Run 2:

  • native (24123) 100%
  • orig quicksort (15903) 65.92%
  • undefined-safe quicksort (15776) 65.4%

New JSBen.ch test

P.S. I dunno why I have got so stuck into this benchmarking :).

Collapse
weeksseth profile image
Caleb Weeks Author

Cool! Thanks for adding those benchmarks! I wonder how it compares to this version:

const qs = (arr) => [...arr].sort((a, b) => a - b);
Enter fullscreen mode Exit fullscreen mode
Thread Thread
darrylnoakes profile image
Darryl Noakes • Edited on

I did it with just .sort() (labeled as native), but I'm not sure how that compares.
It does affect the sort order though: plain .sort() orders it [numbers, nulls, undefineds], while this orders it like the other implementations, with undefineds being put at the end instead of being filtered, i.e. [nulls, numbers, undefineds].

Feel free to write some more benchmarks yourself, if you want :).

I did those on my Pi 4 4GB, which is slowish.
It gets 24k ops/s for native sort while my phone (Galaxy A51 4GB) gets 30k ops/s.

Collapse
weeksseth profile image
Caleb Weeks Author

Thanks for the catch! I'll update!

Collapse
amn3s1a2018 profile image
Amn3s1a2018

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.

Collapse
weeksseth profile image
Caleb Weeks Author

Good catch! Without explicitly comparing against undefined, my version would fail for arrays containing zeros. Since this is a sorting algorithm, I'll assume that an array of numbers is being passed in. I'll update to correct it!

Collapse
amn3s1a2018 profile image
Amn3s1a2018 • Edited on

Sorry, i just replaced your original bug with a bigger one. And maybe i didn't emphasized enough, that those zeros are not just the zeros. Boolean false, empty string and even the document.all (in browser it's an array or object with type of "undefined" – what?) is falsy...

Thread Thread
weeksseth profile image
Caleb Weeks Author

Yeah, that's true. But I guess what should you expect if you try to put a boolean, empty string, or an object in a number sorting algorithm... There is a reason why Array.sort coerces all items in the array to strings.

Collapse
tracygjg profile image
TGJ Gilmore • Edited on

Beautiful. For all its faults, JavaScript does offer a level of versatility uncommon to most languages. That means we can always learn and apply effective and efficient techniques found in other OO or/and FP languages.

Collapse
ashoutinthevoid profile image
Full Name

Cool stuff. Maybe not the most practical, but certainly interesting.

I learned more about Haskell syntax (as, alas, I still haven't 'learned me a Haskell for great good') than anything else, but that's never a bad thing.

Collapse
weeksseth profile image
Caleb Weeks Author

Glad you found it interesting! To be honest, this post is mostly about explaining Haskell in JavaScript terms, and isn't meant to be all that practical.

Collapse
akashkava profile image
Akash Kava

Quick sort done inefficiently = Bubble Sort