Bob Ippolito (@etrepum) on Haskell, Python, Erlang, JavaScript, etc.
«

Comparison and Adaptation in JavaScript

»

JavaScript's comparators are flat out broken. They're marginally useful for value types, but without operator overloading or a sensible default, they're worthless for anything other than checking object identity.

In a language without useful operators, you effectively have to pretend that they aren't there anymore and just do everything with functions. MochiKit is a framework full of such functions that make JavaScript programming bearable. One of the most useful functions in MochiKit is the compare(a, b) function, which will go through the trouble of performing a meaningful comparison between a and b. A meaningful comparison is a function that will do one of the following four things:

  1. Return 0 if they are equal
  2. Return 1 if a is greater than b
  3. Return -1 if a is less than b
  4. throw TypeError if no meaningful comparison between a and b is currently defined

Fresh off the script tag, MochiKit knows how to compare primitive value types (undefined, null, string, number), Array-like-objects, and Date-like-objects. However, the compare function is completely extensible and can be convinced into doing whatever you want it to do. This is probably a little strange to most JavaScript programmers, but what MochiKit uses is a form of multiple dispatch using an adapter registry. compare(a, b) works like this:

  1. Check to see if a == b and return 0
  2. Check to see if a or b is undefined or null. If they are both undefined or null, they are equal. If one of them is undefined or null, then the other value is greater.
  3. Ask the comparator registry to perform compare(a, b) if it can
  4. If not, throw TypeError

The comparator registry is effectively a list of function pairs, [check, wrap]. The check function takes two arguments, and returns true if they are comparable with the paired wrap function. The wrap function returns the value of the comparison. When the comparator registry is asked to perform a comparison, it iterates over all of its function pairs in a particular order like this:

for (var i = 0; i < this.pairs; i++) {
    var pair = this.pairs[i];
    if (pair[0](a, b)) {
        return pair[1](a, b);
    }
}
throw NotFound;

Using this model, we can register arbitrary comparisons between anything and anything else! For example, a comparator registry pair for comparing Date-like objects would look like this:

// the "check" function
isDateLike = function () {
    /***

        Returns true if all given arguments are Date-like

    ***/
    for (var i = 0; i < arguments.length; i++) {
        var o = arguments[i];
        if (typeof(o) != "object" || typeof(o.getTime) != 'function') {
            return false;
        }
    }
    return true;
};

// Register a comparator to compare dates
registerComparator(
    // the name of the comparison (for humans)
    "dateLike",
    // the "check" function
    isDateLike,
    // the "wrap" function
    function (a, b) { return compare(a.getTime(), b.getTime()); }
);

Assuming that registerComparitor adds the given function pair to the comparator registry (which it does, and the tests prove it), the dates can now be compared. You can imagine how useful it would be to add comparators for arrays, and your own custom model objects.

Imagine for a minute that you were doing some kind of search engine, and the score was calculated on the client-side, or you were doing some kind of merge from separate result sets, or it was just too much of a bother to sort the results server-side. Making them sortable is no problem with this infrastructure:

SearchResult = function (text, score) {
    this.text = text;
    this.score = score;
};

registerComparator("SearchResult",
    // "check" function
    function (a, b) {
        // this is really "and", but I'm working around an ampersand formatting bug in the blog...
        return !(!(a instanceof SearchResult) || !(b instanceof SearchResult));
    }
    // "wrap" function
    function (a, b) {
        // assume that arrays can be compared meaningfully; they can.
        return compare([a.score, a.text], [b.score, b.text]);
    }
);

// imagine this is populated like so:
var results = [
   new SearchResult(....),
   new SearchResult(....),
   ...
];

// need to sort?  No problem!  Use the built-in Array.prototype.sort!
results.sort(compare);

A different (and often more appropriate) way to filet this fish would be to simply use a key comparator to do this for you, rather than registering a comparator specific to your types. MochiKit has one of those too. The equivalent (given the same definition of SearchResult and results) would be this:

results.sort(keyComparator("score", "text"));

You can imagine how useful this is for doing sortable tables...