Google
Natural transformations are a foundational construct in category theory, so it seems fitting to follow up my last post by describing one using the categories Html and Jqry. As a result this post assumes the reader has covered the material from the last post. Also, as much as I wish that I could claim a similarly exciting result this will remain mostly an exercise in clarifying what natural transformations are and how they behave. If it's any consolation I've borrowed some very attractive TeX diagrams from Wikipedia to help illustrate.

Natural Transformations

Natural transformations are actually fairly simple once you have an example you can comprehend. One way to describe them is - a set of morphisms1 that reconcile the way two functors from the same source to the same target categories alter morphisms of the source category2. Unfortunately the written descriptions seems to fall short in aiding comprehension, but as promised there are pretty pictures:
n sub x compose F applied to f is equal to G applied to f compose n sub y
This equation is simple and captures the expected behavior of the natural transformation N (used in place of η hereafter). Namely, it must "prepare" input objects for a morphism transformed with G, ie G(f), such that the result will be identical to that of "repairing" the output objects from a morphism transformed with F, ie F(f). Again, this assumes that both F and G share that same source and target categories. Also it helps to remember that the input and output objects of F(f) and G(f) are in the target category, so if F and G are both from categories Html to jQuery we're just dealing with objects in Jqry. If the notation is confusing recall that is the operator form of $.compose and that F(f) is that same as $.Functor(f) from the previous post, both of which result in JavaScript functions/morphisms. While this equation gives us an understanding of how the transformation should function, it doesn't help with comprehending the transformations directionality and purpose.
diagram of composition
Diagrams are used to clarify composition of morphisms, a (the?) key operation in category theory. This diagram represents the same concept as the equation but it makes the goal more obvious: from F(X) whether you take the road to the east - Ny ○ F(f) or the road to the south - G(f) ○ Nx - the result has to be the same. Again, the purpose of the natural tranformation is get the results to look like G(f) results whether the operation started with F(f) or ended with G(f). If, at this point, it's still unclear don't worry the JavaScript examples should help.

Two Functors

Since natural transformations are defined for two functors we'll borrow the $.Functor from the last post and then try to find another. As a quick refresher the $.Functor functor maps from Html to Jqry using the $.fn.map method. We'll rename it F so that it's easier to reconcile with the diagram/equation.
/** @sig {html.morphism | HTMLElement} -> {jqry.morphism | jQuery} */
function F( a ) {
  if( typeof a === "function" ) {
    return function() {
      this.map( a );
    };
  }

  return $( a );
}
The new functor obviously has to be different, so let's tweek the way that it operates on the functions from Html. In this case the function it returns only applys the html.morphism to the first member of the jQuery object's set. Note that it retains the same operation on objects in Html, the application of $().
/** @sig {html.morphism | HTMLElement} -> {jqry.morphism | jQuery} */
function G( a ) {
  if( typeof a === "function" ) {
    return function() {
      a( this[0] );
    };
  }

  return $( a );
}
An alternate implementation that forwards the arguments down to the html.morphism is a bit more complex but much more useful3:
/** @sig {html.morphism | HTMLElement} -> {jqry.morphism | jQuery} */
function G( a ) {
  if( typeof a === "function" ) {
    return function() {
      var args = [].slice.call(arguments);

      args.unshift( this[0] );
      a.apply( this, args );
    };
  }

  return $( a );
}
At first this may seem like defining an alternate functor for the sake of it, but there are already methods in jQuery Core that behave in this fashion. For example a naive implementation of the $.fn.css method using the argument-forwarding form of our new functor4:
$.fn.newCss = G(function( elem, key, value ){
  elem.setAttribute( "style",  key + ": " + value );
  return elem;
});

var $foo = $( ".foo" );           // [<div class="foo"></div>, <span class="foo"></span>]
$foo.newCss( "display", "none" ); // [<div class="foo" style="display: none"></div>,
                                  //  <span class="foo"></span>]
Now we've got two functors that satisfy the basics needed to define a natural transformation. They both have the same source and target categories, Html and Jqry respectively, but they are distinct in the way that they achieve the goal of translating the functions/morphisms from Html into functions/morphisms in Jqry. Now we just need to find a way to make results from F look like results from G.

Finding the Transformation

Recall from the diagram that the natural transformation must produce the same result whether it's composed "in front of" a $.fn method defined with G or after a $.fn method defined with F. Lets look at an example of two methods built with F and G using the css function in the previous example to see if that points us in the right direction. For completeness' sake we need to modify F so that the function it returns accepts arguments:
/** @sig {html.morphism | HTMLElement} -> {jqry.morphism | jQuery} */
function F( a ) {
  if( typeof a === "function" ) {
    return function() {
      var $this = this,
          args = [].slice.call(arguments);

      this.map(function( elem ) {
        args.unshift( elem );
        return a.apply( $this, args );
      });
    };
  }

  return $( a );
}
Having squared that let's look at an example definition of two $.fn methods using the Functors.
var alterCss = function( elem, key, value ){
  elem.setAttribute( "style",  key + ": " + value );
  return elem;
};

$.fn.mapCss = F(alterCss);
$.fn.oneCss = G(alterCss);

var $foo = $( ".foo" );           // [<div class="foo"></div>, <span class="foo"></span>]
$foo.mapCss( "display", "none" ); // [<div class="foo" style="display: none"></div>,
                                  //  <span class="foo" style="display: none"></span>]

var $bar = $( ".bar" );           // [<div class="bar"></div>, <span class="bar"></span>]
$bar.oneCss( "display", "none" ); // [<div class="bar" style="display: none"></div>,
                                  //  <span class="foo"></span>]
Here $.fn.mapCss is equivelant to F(f) and $.fn.oneCss is equivelant to G(f) in the equation and diagram. As you would expect the method created using G only alters the first element in the jQuery object set where as the method created with F alters all the elements. So our hypothetical natural transformation could simply reduce the jQuery object set to the first element in which case both results would be the same. The $.fn.first method should serve. Borrowing the $.compose function, again from the previous post, we can verify that it matches the equation.
$.fn.FtoNy = $.compose( $.fn.first, F(alterCss) );
$.fn.NxToG = $.compose( G(alterCss), $.fn.first );

$( ".foo" ).FtoNy( "display", "none" ); // [<div class="foo" style="display: none"></div>]
$( ".bar" ).NxToG( "display", "none" ); // [<div class="bar" style="display: none"></div>]
If you replace the application of $.compose with the infix operator it looks just like the equation:
n sub x compose F applied to f is equal to G applied to f compose n sub y
With the order reversed we can use the more idiomatic fluent invocation:
$.fn.mapCss = F(alterCss);
$.fn.oneCss = G(alterCss);

$( ".foo" ).mapCss( "display", "none" ).first(); // [<div class="foo" style="display: none"></div>]
$( ".bar" ).first().oneCss( "display", "none" ); // [<div class="bar" style="display: none"></div>]
Let's alter the diagram to use the new method names:
altered diagram
As you can see the southerly route first limits the jQuery object set and then applys the method that only operates on the first object, whereas the easterly route first applys the method that opperates on all the functions in the jQuery object set and then limits the set to one result. Most of the time you'll want to head South to save yourself some execution time.

Naturally

The result of our work is a trivial optimization that most users should be able spot, ie. they might be creating a method chain that invokes $.fn.first too late. In any case, the fact that we can arrive at this conclusion by viewing the JavaScript through the lense of mathematics continues to astound me and it makes me wonder what interesting things I might find by examining Monoids and Cartesion Closed categories.
  1. Thanks to Dan Peebles, otherwise known as copumpkin, for reviewing the introduction to natural transformations and suggesting this addition.
  2. This is far from rigorous. For a more concrete definition checkout the wikipedia page and haskell wiki page pages. My attempt to rephrase the definition comes from my experiences learning abstract concepts like this where I've often been aided by many different renderings of the same idea.
  3. It's important to keep in mind that, as a result of forwarding the arguments, we've technically changed the type signature of the Html morphism from HTMLElement -> HTMLElement to HTMLElement, String, String -> HTMLElement. For the purposes of our discussion I thought it was usefull to pull an existing example from jQuery to illustrate how the second functor works. Also if the jQuery object is empty this will `unshift` undefined as the first argument. Again, clarity proved to be more important.
  4. This implementation omits even simple style persistence for the sake of focusing the reader on the subject matter.

Published

22 Mar 2012

Tags