Saturday, September 18, 2010

Sets in JavaScript

JavaScript does not have a set data type, but it really should. Sadly, I'm not the boss of the world, so I can't require that they add one -- but what I can do is write my own. This is a bit tricky, actually. The standard way of faking sets in JavaScript is to use object properties; something like this:

This is fast, and only a bit ugly. There are a few problems with it, though. First, you don't have the usual set-theoretic operations like intersection, difference, union, and so on. There's no easy way to find the cardinality of the set, unless you maintain a separate counter. You can fix all these by writing a custom set class, but that would take effort.

The second problem with this approach is more serious: object properties in JavaScript must be strings. Anything that's not a string is cast to a string. A proper set data type should be able to have the number 3 and a string '3' in the same set, as distinct members, but both of those get cast to the same string.

What we need, to make a general-purpose set data type, is to use unordered arrays for storage. At least, that's the best option I could come up with that didn't involve making an extension in C. I've written a library to do this, and tested it with Node.js, although it should work on any web browser as well. Here's the repository on GitHub. The code can be very simple:

It supports pretty much the same API as Python's sets module. If you use Node.js, and you have the Node Package Manager, you can install it with "npm install simplesets". If you have any feedback, or want to contribute changes, please email me or fork it on GitHub.