Applications of Category Theory in Modern JavaScript

The Chains That Bind

Figure 1

Ubiquity Thy Name is jQuery

jQuery is an extremely popular open source JavaScript library, dual licensed under the GPL and MIT licenses. Figure 1 shows the percentage use of jQuery among the top ten thousand, hundred thousand, and one millions websites on the internet as ranked by Alexa [!!]. Additionally the project's website sees more than one hundred thousand [!!] unique visits a month from developers all over the world. Given these numbers it's fair to say that jQuery is one of the most popular libraries available to JavaScript developers, and possibly one of the most popular open source libraries available to any developer.

This popularity is due in part to the fluent interface that the library promotes for manipulating the browser's document object model. As with many abstractions that simplify complex data manipulation it often requires performance tradeoffs. Here we identify a subset of chainable jQuery methods that can be optimized in the interest of increasing performance. As a result we derive a simple jQuery extension that can assist developers in identifying when these methods are being used.

Fluent Interface

In Figure 2 you can see an example of a typical DOM manipulation built using jQuery's chainable methods. In this case all the HTMLDivElements are selected from the DOM, hidden, the foo CSS class is added, and they are shown again. Figure 3 shows a "deabstracted" naive implementation of the method chain from Figure 2 , and, as you can see, iterating over the set three times where one would seemingly suffice suggests an opportunity for a performance improvement.

Internally these methods are implemented using for loops or in one of two forms built with jQuery.map and jQuery.each.

jQuery( "div" ).hide().addClass( "foo" ).show();
 Figure 2 
var $divs = $( "div" );

for( var i = 0; i < $divs.length; i++ ) {
  $divs[i].setAttribute( "style", "display: none;" );
}

jQuery.each( $divs, function( element ) {
  element.setAttribute( "class", "foo" );
});

jQuery.map( $divs, function( element ) {
  element.setAttribute( "style", "display: block;" );
});
 Figure 3

Map Form

One of the two general forms that jQuery methods take is referred to here as the "map form". This leverages the jQuery helper methods jQuery.map or jQuery.fn.map to alter each element in the jQuery object set. This is the form with which our work is predominantly concerned due to the way it promotes operations on elements without side effects.

Each & For Forms

The other forms that one might find underlying jQuery methods are the "each form" and the "for form". Here side effects are the order of the day. Either of these forms can be implemented using jQuery.map which provides further motivation in optimizing for the "map form". Figure 5 shows one such implementation

jQuery.map( list, function( elem, i ){
  // manipulate HTMLElement
  return elem;
});


 Figure 4 


jQuery.each = function( list, callback ) {
  jQuery.map( list, function( elem, i ){
    callback( elem, i);
    return elem;
  });
};
 Figure 5

When to Optimize?

Given that many of jQuery's core methods and the thriving plugin ecosystem that accompanies them leverage these forms [!! - possible list them in a figure] there is likely great value in identifying ways to reduce the full number of set iterations made when they are used in chains. Unfortunately the source that makes up these methods is often complex even from the implementors perspective so a rigorous definition of which can be targetted for optimization has value. For that purpose we turn to some rudimentary category theory.

jQuery Iterative Methods

TODO show some percentage of the jQuery api that is iterative. Pie chart?

Categorically Identifiable

Defining Html

The Category Html is extremely simple. The objects in Html are the HTMLElements that the reader may be familiar with from the JavaScript DOM API (eg, HTMLDivElement). The morphisms are JavaScript functions from HTMLElements to to HTMLElements. Next we verify that Html satisfies the three category laws: identity, composition, and closure under composition (Figures 6,7,8).

Defining Jqry

Jqry is the category of jQuery objects and functions from jQuery objects to jQuery objects. It's only slightly more complex than Html because we take this to be an implicit parameter to the JavaScript functions that are the category’s morphisms. Also, these morphisms must be defined on the jQuery.fn object to guarantee the value of this is a jQuery object.

function id( a ) {
  return a;
}


 Figure 6 
function cmps( f, g ){
  return function( a ) {
    return f(g(a));
  };
}
 Figure 7 
$.fn.id = function(){
  return this;
};


 Figure 9 
$.cmps = function( f, g ){
  return function(){
    return f.apply(g.apply(this))
  };
};
 Figure 10

The identity function is trivial and function composition is always associative. We know that the morphisms in Html are closed under composition because the functions accept as their only argument HTMLElements and return only HTMLElements. Having met the three requirements for a category with Html we can move on to the second, and more complex category Jqry.

The value of this, and the constraint that the morphisms must be defined on jQuery.fn, play an important role in the way that the morphisms of Jqry behave. The prototype of all jQuery objects is $.fn, meaning when you call $("div").foo() it finds foo on the $.fn by following the prototype chain.

function a( elem ){
  elem.setAttribute( "foo", "bar" );
  return elem;
}

function b( elem ){
  elem.setAttribute( "baz", "bak" );
  return elem;
}

var elem = document.getElementById( "sample" );
elem = cmps( a, b )( elem );
elem.getAttribute( "foo" ); // "bar"
elem.getAttribute( "baz" ); // "bak"
 Figure 8 
$.fn.a = function(){
  // a from  Figure 8 
  return jQuery.map( this, a );
};

$.fn.b = function(){
  // b from  Figure 8 
  return jQuery.map( this, b );
};

var $elem = $( "#sample" );
$.fn.aAndB = $.cmps( $.fn.a, $.fn.b );
$elem.aAndB().attr( "foo" ); // "bar"
$elem.attr( "baz" );         // "bak"
 Figure 11

Notice the use of a and b from the Html cmps example in Figure 8 for the functions that are mapped using jQuery.map over the set of elements in the jQuery objects in Figure 11 . This plays an important roll in understanding the Functor from Html to Jqry.

Composition works by taking the first function, g, in Figure 10 and explicitly defining its this value using the apply method. The return value is a jQuery object which is used to define this in the application of f. As a result, we know that the morphisms of Jqry are closed under composition because each accepts and returns only jQuery objects.

Defining a Functor

The benefits of providing these two categories are realized in a Functor from Html to Jqry. jQuery's constructor, nearly always aliased as $, transports the objects from Html ( Figure 12 ) and jQuery.map partially applied to this transports the morphisms ( Figure 13 ).

var htmlObject = document.getElementById( "sample" );
var jqryObject = $( htmlObject );
 Figure 12 
function F( htmlMorphism ) {
  return function() {
    return jQuery.map( this, htmlMorphism );
  };
}

// a from  Figure 8 
$.fn.a = F(a);
jqryObject.a().attr( "foo" ); // bar
 Figure 13

Fuse with Confidence

The fact that the functor distributes over composition (Figure 14) suggests that jQuery methods using jQuery.map with composed Html morphisms can be relied upon to behave identically to chains of their transported Jqry morphism counterparts. The reader may recognize this simply as loop fusion. With a rigorous understanding of which Jqry morphisms can be fused we can begin to define a standard and helper libraries to assist the end user in optimizing their jQuery method chains.

cmps(F(a), F(b))       == F(cmps(a, b));
$.cmps($.fn.a, $.fn.b) == F(cmps(a, b));
jqryObject.b().a()     == jQuery.map(jqryObject, cmps(a, b));

Figure 14