Disable Your Links, or Gate Your Functions?

It’s pretty common to disable links and buttons that cause updates, so those updates don’t happen twice, and re-enable them when the update has finished.

At work, our app’s links are usually wired to javascript functions that use jQuery to scrape the form data and post it to web services via ajax. We normally disable links and buttons something like this:

var updateLink = $('#updateLink');  // Find the link.
updateLink.click(function() {       // When it's clicked...
   updateLink.disable();            // disable it...
   ajax({
      data: getFormData(),          // ... & send the form data
      url: 'http://someWebService', // to some web service.
      success: function(results) {  // When the service
         if (results.hasErrors) {   // finishes,
            showErrors(results);    // show any errors,
            updateLink.enable();    // and enable the link
         }                          // so they can try again.
      }
   });
});

We added those enable() and disable() functions to jQuery — they just add or remove the disabled attribute from whatever they’re called on. But it seems Firefox doesn’t support disabled on anchor tags, like IE8 does, so we couldn’t stop the repeat-calls that way.

We got to thinking, what if the link always called its javascript function, but the function could turn itself off after the first call, and back on after a successful ajax post? That led to this:

function makeGated(fn) {
   var open = true;
   var gate = {
      open: function() { open = true; }
      shut: function() { open = false; }
   };

   return function() {
      if (open) {
         fn(gate);
      }
   };
}

makeGated takes your function, and wraps it in another function, a gate function (it “makes your function a gated function”). When you call the function it creates, it will only call your function if the gate is open — which it is, at first. But then, your function can decide whether to close the gate (that’s why the gate is passed to your function). You could use it like this:

var updateLink = $('#updateLink');  // Find the link.
updateLink.click(
   makeGated(function(gate) {       // When it's clicked...
      gate.shut();                  // shut the gate...
      ajax({
         data: getFormData(),       // ...same as before...
         url: 'http://someWebService',
         success: function(results) {
            if (results.hasErrors) {
               showErrors(results);
               gate.open();  // Open the gate
                             // so they can try again.
            }
         }
      });
   }));

We dropped this in, and it worked pretty much as expected: you can click all you want, and the update will only fire once; when the update completes, it’ll turn back on.

The downside? Since it doesn’t disable the link, the user has no idea what’s going on. In fact, since the closed-gate function finishes so quickly, it seems like the button’s not doing anything at all, which might even make it look broken.

So we chucked it, and hid the links instead. It’s not as nifty, and it’s not reusable, but it’s clear enough for both end-users and programmers who don’t grok higher-order functions. Even when you have a nice, flexible language, and can make a sweet little hack, it doesn’t mean the dumb approach won’t sometimes win out.

Advertisements

Where the Abstraction Leaks: JavaScript’s Fake Arrays

Ruby arrays have a nice feature: you can construct a new array with an integer N, and a block, which will be called N times, to fill up the array:

Array.new(5) { 'yo' }
# gives:
["yo", "yo", "yo", "yo", "yo"]

# Closures, too!
i = 0
Array.new(4) { i = i + 1 }
# gives:
[1, 2, 3, 4]

I tried to recreate this in JavaScript:

new Array(5, function() { return "drip"; });
// gives:
[5, function() {
    return "drip";
}]

Oops! I guess the Array constructor works differently in JavaScript. No worries, we can just call map on the new array.

new Array(5).map(function() { return "drip"; });
// gives:
[, , , , ]

…um, what? Shouldn’t that be ["drip", "drip", "drip", "drip", "drip"]? If I call new Array(3), I should get a brand new array, with 3 slots, all set to undefined; and I should be able to map over it, and fill up the array.

Let’s see what its elements are:

var array = new Array(5);
array[0]; // undefined, as expected
array[1]; // also undefined

So far, so good. What arguments are passed to the function?

function printAndDrip(arg) {
    print(arg);
    return "drip";
}
array.map(printAndDrip); // prints nothing, and returns [, , , , ]

It looks like the printAndDrip function is never being called, almost like the array has no contents.

Let’s try setting a value manually, then mapping:

array[2] = "hey there"; // [, , "hey there", , ], as expected
array.map(printAndDrip);
// prints "hey there", and returns [, , "drip", , ]

So, it only calls the function for values we’ve manually put there. Maybe map doesn’t call the function if the value of a slot is undefined? I know, I’m reaching here…

array = [1, undefined, 2];
array.map(printAndDrip);

/* prints:
1
undefined
2
then outputs:
["drip", "drip", "drip"]
*/

So it does call the function for undefined values! Then why didn’t it in our newly-created array?

This is when it hit me, and it’s a funny JavaScript fact that I always forget: JavaScript has fake arrays.

They’re actually closer to hash tables, whose keys are numbers. ["zero", "one"] is just syntax sugar: it creates an object with two properties, named 0 and 1; 0 points to “zero”, and 1 points to “one”.

// pretty much the same:
var arrayLiteral = ["zero", "one"];
var objectLiteral = { 0: "zero", 1: "one" };

Apparently, if you use the new Array(10) constructor, it creates an array with length 10, but with no named properties.

We can see the properties an object has with the hasOwnProperty method, so we can use that to test our hypothesis.

var emptyArray = new Array(10);
emptyArray.hasOwnProperty(0); // false
emptyArray.hasOwnProperty(1); // false

var fullArray = [1,2,3];
fullArray.hasOwnProperty(0); // true
fullArray.hasOwnProperty(1); // true
fullArray.hasOwnProperty(99); // false: gone past the end

So where does that leave us? Nowhere, really. At least I’m a little clearer about JavaScript’s fake arrays. Imitating Ruby’s Array constructor is pretty much out; it’s easy enough, though a bit unsatisfying, to hand-roll our own:

Array.filled = function(n, fn) {
    var array = [];
    while(n-- > 0) {
        array.push(fn());
    }
    return array;
}
Array.filled(5, function() { return "drip"; });
// gives:
["drip", "drip", "drip", "drip", "drip"]

Perhaps the folks working on the new JavaScript standards can put in a line-item about initializing Arrays with all the right numbered slots, and that’ll be unnecessary.

While writing this post, I used the JavaScript Shell 1.4 in FireFox 3.6.3 on Windows 7. I also redefined Array.prototype.toString to display JavaScript arrays the way you type them.

Array.prototype.toString

This is one of my favorite javascript tricks, because of its effort-to-payoff ratio.

Problem: the default Array.prototype.toString hides any nested structure.

[1, 2, 3, 4, 5].toString(); //-> "1, 2, 3, 4, 5"
[1, 2, [3, 4], 5].toString(); //-> "1, 2, 3, 4, 5"

Solution: override Array.prototype.toString.

Array.prototype.toString = function() {
    return '[' + this.join(', ') + ']';
};

[1, 2, 3, 4, 5].toString(); //-> "[1, 2, 3, 4, 5]"
[1, 2, [3, 4], 5].toString(); //-> "[1, 2, [3, 4], 5]"

A JavaScript War Story

What follows is an account from the author’s experience. Some details have been changed for the usual reasons, and a poor memory has fuzzed out the rest.

UPDATE: it turns out the technique described below is known as debouncing. What an awesome name!

My last job was for a company that made case-management software. With this software, you could track all kinds of data about your case: you could categorize it, sub-categorize it, say where and when it happened, note whether it was still open, track who was responsible…all kinds of stuff, great for data fiends.

One of our customers’ favorite features was the reports, and they were pretty spiffin’. But, not being ones to rest on our laurels, we were adding pivot-table reports, so you could count the number of cases, grouped by any criteria you wanted. The input screen let the customer pick their pivot criterion, and which criteria they wanted as columns, for sub-counts. We struggled to name these UI fields — something lucid, something explanatory, something evocative — something to make them understand what kind of report they were in for. After a while, we decided to just show them: when they changed their pivot criterion, we’d run some javascript to render a skeleton report, same as the real report, but minus the data. It would save them time, and save our servers.

The javascript was pretty involved. It had to generate the same HTML as we did for the pivot table, which meant it had to know (or make up) values for each criterion, like all the case categories and sub-categories, and which sub-categories belonged to which categories. And we let the customers pivot on up to THREE, count ’em, different criteria. And it had to happen each time the user picked different pivot criteria. It took a few tricks, but we got it working. It ran slowly, maybe a few seconds, but it was quick enough, probably, especially once we threw in a little “please wait” spinner. Then we realized we needed to re-render whenever the window resized.

No biggie, I thought, and I quickly added window.onResize(reportPreview);. It worked great, except it re-rendered the report with every pixel-wide movement of the mouse, as the window was dragged to new widths and heights. Calling a function, one that runs for a few seconds, a hundred times in the time it took to widen the browser an inch, meant a locked browser. It meant “time to get more coffee,” and after, “time to fix the bug.”

I knew we could delay calling reportPreview, but we only wanted to delay it when the window was being resized — when the user changed the columns, there was no reason to wait. I was sure window.setTimeout() would do what we needed, but I didn’t want to muck up reportPreview() with it.

I’d been reading The Little Schemer lately, and noticing some striking similarities between javascript and scheme: first-class functions, and higher-order functions that take functions as arguments, and return other functions as values. It was fun reading, with its strange teacher-student dialog style. The material was better than brainteasers, and I knew it would make me a better programmer down the road, but I didn’t think of it as relevant to the day-job, as…applicable.

Then I realized higher-order functions were a way out of this. I could write a function, delay, that would wrap one long-running, slow-poke function in another function: an intermediary that you could call as many times a second as you wanted, but it would only call the slow-poke once things had settled down. delay would let us keep setTimeout out of reportPreview. Something like this:

function delay(millis, slowPoke) {
    var timeoutId = undefined;

    // This is the intermediary.  Call it lots, it won't hurt.
    return function() {
        if (timeoutId) {  // If we're waiting...
            clearTimeout(timeoutId); // re-start the clock.
        }
        timeoutId = window.setTimeout(slowPoke, millis);
    }
}

The first time you call the intermediary, it tells the window to call slowPoke after a bit, but every time you call it after that, it starts the clock over. It’s like when you’re in a five-minute time-out, and you start acting up after only three, so your mom says “Ok, buster, another five minutes.”

var fiveMinutes = 5 * 60 * 1000;
var screamAndShout = delay(fiveMinutes, function() {
    getBackToPlaying();
});

screamAndShout(); // Aw nuts, I'm in time-out.

// I'll be good for as long as I can, but...
screamAndShout(); // dang, five MORE minutes!

Once delay was in place, running reportPreview when the window was resized was no problem.

function reportPreview() {
    // recursion, DOM manipulation, insanity...
}
columnPicker.onChange(reportPreview);
window.onResize(delay(100, reportPreview));

After testing, we found that delaying it for 100 milliseconds made all the difference in the world.

Do you have a war story? Share it, and start the healing: tell a short one in the comments, or link to a longer one on your own damn blog.

Continuations: a warm-up

Continuations and continuation-passing style (CPS) are introduced in The Little Schemer, chapter 8, using collectors: functions that collect values, through being repeatedly redefined. It was a tough chapter for me, but the idea is simple once you get it, so I’d like to leave some help for others. I’ll use Ruby for the examples, with some JavaScript and Scheme at the end.

In languages with first-class functions, you can assign functions to variables, and re-assign those variables. Consider this Ruby example:

func = lambda { |x| puts x }

['a', 'b', 'c'].each { |ch|
    old_func = func
    func = lambda { |x| old_func[x + ch] }
}

func['d']  #=> prints 'dcba'

By re-defining func in terms of old_func, we’re building up a recursive computation. It’s like normal recursion, but approached from the other side — without explicit definitions. Since a Ruby function is a closure, it remembers the value of the variables in scope when it was created; each layer of this recursion holds its own value for ch and old_func. When we call the last func, it sees ch = ‘c’ and x = ‘d’. It concatenates them, and calls its version of old_func…which sees x = ‘dc’ and ch = ‘b’, concatenates them, and passes it to its old_func, and so on.In fact, if we wrote it like this, the execution of all those lambdas would be exactly the same:

func_puts = lambda { |x| puts x }
func_add_a = lambda { |x| func_puts[x + 'a'] }
func_add_b = lambda { |x| func_add_a[x + 'b'] }
func_add_c = lambda { |x| func_add_b[x + 'c'] }
func_add_c['d']  #=> prints 'dcba'

We could calculate factorials this way:

def factorial(n, func)
    if n == 1
        func[1]
    else
        factorial(n - 1, lambda { |i| func[i * n] })
    end
end
factorial(3, lambda { |fact| puts fact })  #=> prints 6
  1. On the first call to factorial, n = 3, and func just prints its argument. But func isn’t called yet…since n isn’t 1, we recurse with n - 1 = 2, and a new function that calls func with its argument i times 3.
  2. On the recurse, n = 2, and func calls the original printer func with its argument i times 3. Since n still isn’t 1, we recurse again, with n - 1 = 1, and a new function that calls our func with its argument i times 2.
  3. On the final round, n = 1, so we (finally!) call func with 1, which…
  4. …calls the previous func with 1 * 2, which…
  5. …calls the original func with (1 * 2) * 3, which…
  6. prints 6.

As factorial recurses, it builds up a recursive tower of func calls. In factorial‘s base case, the last (and outermost) func is called, and we begin to climb down the func tower, to its bottom floor, the original func. It’s recursion in two directions.

In case Ruby isn’t your favorite language, here are versions in JavaScript and Scheme:

function factorial(n, func) {
    if (n == 1)
        func(1)
    else
        factorial(n - 1, function(i) {
            func(n * i)
        });
}

factorial(3, function(fact) { print(fact) })
; Too bad WordPress doesn't format Scheme or Lisp!
(define factorial
  (lambda (n func)
    (cond ((= n 1) (func 1))
          (else (factorial (- n 1)
                           (lambda (i) (func (* n i))))))))

; Here, the original func is just an identity function.
(factorial 4 (lambda (fact) fact))

Once this is clear, you can see many other applications:

  • You could find all the even numbers in a list: instead of passing a number to func, pass the list of even numbers, and add each even number in.
  • You could separate the numbers into evens and odds: instead of passing just one list to func, pass two lists, for evens and odds, and add each number to the correct list.
  • You could separate any list of items by any criteria: instead of hard-coding “is even?” into the function, pass a predicate function. (Maybe you want to extract all occurrences of ‘tuna’ from a list of words.)

That should be enough of a warm-up for chapter 8. See you in chapter 9, when they derive the Y-combinator!

Regular Expressions into lambdas: swapper, stripper, scanner

Here’s some light Friday fun… When working in ruby with regular expressions on Arrays of Strings, I get so tired of doing this:

my_array.map! { |item|
    item.gsub(/delete this/, '')
}

Can’t we just give the regex to the array, and let it figure it out? How about this:

class Regexp
   def stripper
      lambda { |s| s.gsub(self, '') }
   end
end

my_array.map!(&/delete this/.stripper)

We can generalize it to use any string as the replacement:

class Regexp
   def swapper(new_s)
      lambda { |s| s.gsub(self, new_s) }
   end
   
   def stripper
      swapper ''
   end
end

my_array.map!(&/delete this/.stripper)
my_array.map!(&/replace this/.swapper('with this'))

Which gets me thinking…what if we want to extract text by a regexp?

class Regexp
   def scanner
      lambda { |s| s.scan(self) }
   end
end

my_array.map(&/[find pattern]/.scanner)

What else can we do with regular expressions?

As a bonus, this translates nicely into JavaScript, too:

RegExp.prototype.swapper = function(new_s) { 
   re = this
   return function(s) {
      return s.replace(re, new_s) 
   } 
}

RegExp.prototype.stripper = function() { 
   return this.swapper('')
}

// Don't forget those closing parens...
my_array.map(/delete this/.stripper())
my_array.map(/replace this/.swapper('with this'))

Why Functional JavaScript?

I’m teaching myself functional programming (FP). I first noticed it in Ruby, even though it’s been in JavaScript all along. I’m working my way through Structure and Interpretation of Computer Programs (SICP), and The Little Schemer books, so I’m learning Scheme and Lisp too.

When studying FP, I generally use JavaScript and Scheme. My FP examples here are usually in JavaScript:

  • It’s available everywhere, and most programmers are comfortable reading it.
  • It’s closer to Scheme than Ruby is, so the examples translate better. In fact, Douglas Crockford notes: “JavaScript has much in common with Scheme. It is a dynamic language. It has a flexible datatype (arrays) that can easily simulate s-expressions. And most importantly, functions are lambdas. Because of this deep similarity, all of the functions in The Little Schemer can be written in JavaScript.”

I include Ruby or Scheme, though, if it seems appropriate.

I often use the JavaScript Shell, or its big brother, the JavaScript Development environment, because I haven’t found or built a JavaScript REPL as nice as Dr. Scheme.

Performance

Most current JavaScript implementations are slow with recursion and closures…two cornerstones of functional programming.

I don’t worry about this, because my examples are not meant to be dropped into production systems without thought and testing. I write production-ready code at work; here, I play and explore. We do use some functional JavaScript where I work, but it’s where the performance is acceptable, and the imperative alternative would be too unwieldly.

History seems to show that performance is a short-term concern, and better programming techniques are a long-term concern. It also seems that there are no inherent reasons JavaScript is slow; more performant implementations may be in our future.

Why not Haskell or Erlang?

…or OCaml, Scala, F#, Clojure? I’m getting there. SICP and The Little Schemer books are more than enough for me right now.

Functional Programming in JavaScript and Ruby

[UPDATE: I’ve been lucky enough to have some commenters who know much more about functional programming than I do. There’s some good reading in the comments, and you especially should read them before using this stuff in production.]

I’ve been playing with functional JavaScript tonight. It’s not the greatest of OO-functional hybrid languages, but it’s good to supplant my fledgling functional skills with something besides Ruby. Plus, I’m not the only one doing it, so I can compare notes. And who doesn’t love JavaScript, right? …right?

Before I get much farther, I should thank Adam Turoff for his post What’s Wrong with the For Loop. It gets at the root of the why we’d use a functional programming language instead of an OO or procedural one, and (bonus!) it helped me grok Ruby’s inject method (it’s the same as my new friend fold). Go read his post, it’s good for you. And if you like it, we recommend the 1981 SICP lectures. Robusto!

Here we go!

Introductions to functional programming usually discuss three methods: map, find, and fold. The names aren’t always the same, but those are the three amigos of functional programming. They all do something different to arrays (or lists, or collections, or whatever you want to call them):

  • find does what it says. You give it some criteria, it returns all the matching elements. The criteria is expressed as a function, a little bit of code that says “yes, I want this one,” or “no, skip it.” If we’re picking out the red gumballs, you could say (in Ruby) gumballs.find_all { |ball| ball.isRed? } find is also known as filter. [Ruby only calls it find_all because it uses find for returning just the first match.] Po-tay-to, po-tah-to.
  • fold takes each element, and “folds” it into a running total. Think of summation—you’re folding each new number into a running tally. In Haskell (and, it seems, many functional languages), it comes in two varietes, fold_left and fold_right, which just mean “start from the left” and “start from the right”. Ruby calls it inject, which confuses some people (like me).
  • map is the mathiest of them (don’t be scared, it’s easy!). In English, we’d say “change each item like this, and give me the new results.” Let’s down-case a list of words. “Change each word to lowercase, and give me the downcased words.” words.map { |word| word.downcase }. The name “map” comes from functions in math (surprise), where you map each input to one output. The whole y = f(x) thing…f is for “function”. Ruby also calls this collect.

Now, none of these comes predefined in JavaScript. How can this be? Well, all the JavaScript engines out there are in browsers, and we know that “when browser elephants battle, it is the JavaScript grass that suffers.” The browser developers are busy with other things. But this oversight means we have some easy examples to write. It’s boring to re-implement existing stuff, just for the exercise. So here we go—I’ll compare examples in JavaScript and Ruby.

A quick word about JavaScript’s open classes

JavaScript has open classes, just like Ruby. In other words, you can re-open a class definition, give it a method, and then start using that method on instances of that class. JavaScript’s OO is prototype-based, not class-based, so it looks a little weird:

Array.prototype.first = function() {
    return this[0];
}
[1, 2, 3].first();  // 1

Array.prototype.rest = function() {
    return this.slice(1);
}
[1, 2, 3].rest();  // [2, 3]

Array.prototype.isEmpty = function() {
    return this.length == 0;
}
[].isEmpty();    // true
[1].isEmpty();   // false

“For the prototypical Array, the Array from which all other Arrays spring forth, create a property called ‘first’, which shall be this function, which returns the first element of the Array…” Just a Biblical way of defining a method for a class.

Open classes is good news, because it’ll make our job of adding map, find, and fold possible, since they’ll be going into the Array class.

Find

find is the easiest, so we’ll start there. Let’s take a look:

Array.prototype.find = function(isAMatch) {
    var matches = [];
    for (i = 0; i < this.length; i++) {
        if (isAMatch(this[i])) {
            matches.push(this[i]);
        }
    }
    return matches;
}

find is a function, and it takes the function isAMatch as a parameter. One of the hallmarks of the functional programming style is that functions are first-class citizens in the language: they can be treated like any other variable, so they can be passed around as parameters, and returned from other functions. [Closures and anonymous functions are also major features.] isAMatch is a function that tells you whether we should include any given element of the Array. Use find like this:

var evens = [1, 2, 3, 4, 5].find(
    function(i) {
        return i % 2 == 0;
    }
);

function isOdd(i) {
    return i % 2 != 0;
}
var odds = [1, 2, 3, 4, 5].find(isOdd);

The first example uses an in-line, anonymous function; the second uses a named function. Both work fine, but here is where we start to see JavaScript’s awkward syntax get in the way. Consider the Ruby version:

# find_all comes pre-defined in Array, via the Enumerable module,
# but this is what it would look like...
class Array
  def find_all
    matches = []
    self.each do |item|   # Ruby says 'self', not 'this'.
      if yield(item)      # yield says "Call the block we were given"
        matches.push(item)   # Stuff item into matches
      end
    end
    return matches
  end
end

evens = [1, 2, 3, 4, 5].find_all { |i|
  i % 2 == 0
}

def isOdd(i)
  i % 2 != 0
end

odds = [1, 2, 3, 4, 5].find_all { |i|
  isOdd(i)
}

In Ruby, every expression returns a value, so return disappears. And Ruby’s blocks mean we don’t need to wrap our match condition inside function(i) { ... }. But Ruby’s find_all won’t take a reference to a method as a parameter:

def isOdd(i)
    i % 2 != 0
end

odds = [1, 2, 3, 4, 5].find_all(isOdd)
# gives error: `isOdd': wrong number of arguments (0 for 1) (ArgumentError)

Once you’ve defined a function in JavaScript, you can pass it around by name, like any other variable, but you need that function(i) { ... } syntax around your test. In Ruby, find_all takes a block instead of parameters, so you can’t pass a reference. Given how nice blocks are in Ruby, I guess this can be forgiven, but it’s a little weird.

Fold

Now we’ll get into the recursive guys. find is a pain to implement recursively in JavaScript, so I did it iteratively, but recursion works well for fold and map. Since recursion seems to be more idiomatic in functional languages, we’ll use it here.

I took two shots at fold in JavaScript (I’m learning). Here they are:

Array.prototype.fold_recursive = function(combineFunc, base) {
    if (this.isEmpty()) {    // I added isEmpty, first, and rest, as above
        return base;
    }
    else {
        return combineFunc(
            this.first(),
            this.rest().fold_recursive(combineFunc, base));
    }
}

Array.prototype.fold_iterative = function(combineFunc, tally) {
    if (this.isEmpty()) {
        return tally;
    }
    else {
        return this.rest().fold_iterative(
            combineFunc,
            combineFunc(this.first(),
                        tally));
    }
}

The first is straightforward recursion. If the list is empty, we’re done, so return the base value (zero, if we’re adding). Otherwise, combine the first value with whatever the rest of the items fold up to. [If you have trouble writing recursively, this is the canonical pattern you should probably follow: if done, do base case; else, do this element, then the rest of them.]

The second is a little different. You’ve got a starting base, the tally so far, and a combineFunc that folds each value into the tally. If the list is empty, we’re done, so return the tally. Otherwise, fold the first item into the tally for the rest of the list.

It the first, you hang around, waiting for the answer to the rest of the problem, before you add in your part of the sum. In the second, you push your part of the sum down into the next round of processing, so you don’t have to remember anything. When the answer comes back from the recursive call, it’ll already have your part of the sum in it.

[The first one is a “linear recursive process”, the second is “linear iterative process”, even though both are recursive procedures. If your interest is piqued, check out this SICP page, but it’s not needed for this article. For the rest of this post, I’ll be using the linear recursive version, because it’s conceptually clearer. Thanks to mfp for keeping me honest.]

Here’s how fold is used:

// A handy adding function
function add(a, b) {
    return a + b;
}

Array.prototype.sum_recursive = function() {
    return this.fold_recursive(add, 0);
}
[1, 2, 3].sum_recursive();  // 6

To sum the elements of an array, we want to fold the numbers together by add-ing them, starting at 0. Easy, isn’t it?

Here are two Ruby versions, based on fold_recursive…one that takes a function (called a “procedure object” in Ruby) as a parameter, one that takes a block:

class Array
  def rest     # We'll define rest, to keep the examples similar
    self[1..-1]
  end

  def fold_w_proc(combineFunc, base)
    if self.empty?
      base
    else
      # "func.call(args)" instead of JavaScript's "func(args)"
      combineFunc.call(
        self.first,
        self.rest.fold_w_proc(
          combineFunc,
          base)
        )
    end
  end
  
  def fold_w_block(base, &combineFunc)
    if self.empty?
      base
    else
      combineFunc.call(
        self.first,
        self.rest.fold_w_block(
          base,
          &combineFunc)
        )
      end
  end

  def sum_w_proc
    fold_w_proc(lambda { |a, b| a + b }, 0)
  end
  def sum_w_block
    fold_w_block(0) { |a, b| a + b }
  end
end

[1, 2, 3].sum_w_proc    # 6
[1, 2, 3].sum_w_block   # 6

Notice how similar fold_w_block and fold_w_proc are to the JavaScript fold_recursive. The thing that differentiates fold_w_block and fold_w_proc is how they’re used. The definitions themselves are nearly identical, except for the order of the parameters. Look at sum_w_proc and sum_w_blocksum_w_block is a bit clearer, isn’t it? But if you use blocks, you lose the ability to pass a function reference as a parameter.

Map

map looks a lot like fold.

Array.prototype.map = function(mapFunc) {
    if (this.isEmpty()) {
        return this;
    }
    else {
        return [mapFunc(this.first())].concat(
                this.rest().map(mapFunc));
    }
}

function cube(i) { return i * i * i; }

[1, 2, 3].map(function(i) { return i * i; });  // [1, 4, 9]
[1, 2, 3].map(cube);  // [1, 8, 18]

Again, it’s basic recursion…if we’re out of items, return the empty list (ie, this). Otherwise, make an array of the first mapped item, and concatenate it with the rest of the mapped items. Again, with JavaScript, you can pass your function in-line, or by reference.

Here’s a recursive definition of map in Ruby:

class Array
  def map(&mapFunc)
    if self.empty?
      self
    else
      [mapFunc.call(self.first)] + self.rest.map(&mapFunc)
    end
  end
end

[1, 2, 3].map { |i| i * i }  # [1, 4, 9]

As before, calling map with a block certainly looks nicer than by passing in functions, but you lose the ability to define a function somewhere, and pass it in by name, like we did with cube in JavaScript.

Wrap-up

If you want to explore functional programming, both JavaScript and Ruby are good candidates. They both have their goods and bads. Up to now, I’ve only used Ruby, but JavaScript certainly has its benefits, and exposure to both balances out my understanding.

I hope that, if you were curious about functional programming before, this was a helpful read. If you’re a functional programmer, and I got something wrong, please let me know…I’m still learning. For instance, I now better understand how recursive processes differ from linear recursive processes.

Examples of DOM Hacking

Finally! You can see a full-blown example of the techniques I’ve been discussing here (the code’s for IE only).

Sorry this took awhile, I’ve been a little behind lately. The good news is the code took me all of an hour to sling together…the real time was spent organizing, cleaning, and documenting it so it’s easy to follow.

DOM hacking is of course most widely used as part of Ajax, to update the page with whatever data the asynchronous HTTP call brings back — but you can still do a lot without ever leaving the client. For example, check out the JavaScript Tabifier. I haven’t looked at the code too much, but it looks like it’s in a similar vein.

There’s also code to make HTML tables sortable from Kryogenix.com, which I’ve used before — very handy. I believe it uses some of the same techniques. Maybe I’ll look them both over, and do a compare/contrast with what I’ve written here.

Practical Applications of Browser DOM Hacking

I’ve been talking about hacking the browser’s DOM lately. Now, here are some situations where this might be useful — but I’ll only lightly cover them, and leave further exploration up to you. [Not because I’m trying to be clever and educational, but because Blogger strips out bunches of my HTML snips, even if I use escape chars. If you have any suggestions, I’m all ears.] Ok, practical applications of new knowledge, here we go!

Generate a Table of Contents

Suppose we have some ordinary HTML: some h1s, h2s, h3s, ps, and imgs. Maybe we’ve thrown in some handy CSS, so it looks nice. Now we want to generate a table of contents at the top of the page, so changes to the contents are automatically reflected above. Let’s say headers make up the links in the table of contents.

Using the getElements() function from last post, we can get an Array of all the header nodes:

var headers = getElements(
    function(node) {
        return node.nodeName.length == 2 &&
        node.nodeName.charAt(0) == "H";
    });

Now, we can create a TOC that lists each header. At the top of the page, create and insert a div to hold the table of contents — let’s call it tocDiv. Then, for each header node, do two things:

  1. Insert an anchor into tocDiv. Set its href to '#' + header.innerText. Add to it a text node (using document.createTextNode()) containing the header’s innerText.
  2. Insert a named anchor right before the header, using header.parentNode.insertBefore(). Set its name to header.innerText, so the TOC link points to it.

Now, at the top of the page, you have a list of links…each one linking to a header tag below, with the same text as the header it links to. You can do some neat formatting with CSS, too…for the tocDiv links, set their CSS class attribute to something like 'toc_' + header.nodeName. Then add CSS class definitions for toc_h1, toc_h2, etc, to make it look more like an outline (you know, make the h1’s big and bold, the h2’s smaller, that kind of thing). If you want to get really fancy, you can wrap each header node in an anchor that links up to the table of contents…even give it a title of “Back to Table of Contents” using node.setAttribute("title", "Back to Table of Contents").

Make a “List of figures”, and put captions on images

This one’s also geared towards creating an outline, and will be pretty similar to the table of contents. Suppose you have images that aren’t there for decoration or formatting, but are supposed to convey information (diagrams, charts, etc). Let’s assume that each has a meaningful alt tag. We can create a list of figures that lists the title of the image (i.e., the alt text), and links to it.

First, like we did for the table of contents, insert a node into the document to hold your list of figures. Let’s say it’s a div called figList.

Get all the images using document.getElementsByTagName("img"), and make a link pointing to each one. For each img node, again do two things:

  1. Add an anchor to figList. Get the img’s alt text via img.getAttribute("alt") — then use it for the anchor’s text, and set the anchor’s href to '#' + altText.
  2. Insert a named anchor before each img node, and set its name to altText.

Adding captions is really simple. While you’re looping through the list of img nodes, insert a span after each one, with class set to “caption”. Set the text to "Figure " + i + ": " + altText, and you’ve got automatically numbered caption images.

Format hyperlinks based on where they lead

I think I read a Jakob Nielsen article that suggested telling users before they click on a link that it’ll take them to another site. Why not put an icon next to each link whose href starts with “http://&#8221;?

var externalLinks = getElements(
function(node) {
// nodeType == 1 means it’s an Element
if (node.nodeType == 1 && node.nodeName == “A”) {
return node.getAttribute(“href”).indexOf(“http://&#8221;) <= 0; } }); [/sourcecode] Using AJAX, you can get really crazy — make a server-side component that returns the file size of a given URL. Now, grab all the links that point to a .pdf, .doc, .zip, or whatever, get the actual size from the server, and tell the user up-front how big the file is.

Checking our sanity

Just to reiterate, we’re talking about changing the HTML structure at runtime. Let’s step back a sec and talk about that.

  1. The server delivers a stream of text to the browser.
  2. The browser parses it and builds a “mental” model of what it says.
  3. The browser renders some text and color on the screen based on that model.

We’re talking about changing that model around at runtime, not the bytes sent to the browser. This means that if you View > Source on your page, you’ll see the original HTML, and none of the fancy nodes you added or rearranged.

To help us see the havoc we’ve wreaked on the DOM, we can hack up a simple bookmarklet to dump out the DOM as HTML in a new window. It’s as easy as this:

  • open a window
  • write out a big textarea to it (use style="width:100%;height:95%")
  • fill the textarea with this window’s document.documentElement.innerHTML

Closing thoughts

There are some general ideas that I’m using in many of these suggestions:

  • Use CSS classes, sometimes named after the node name, to keep your HTML-generating JavaScript clean.
  • Use plain text for named anchors, like header.innerText or img.getAttribute(“alt”). In programming, we usually shy away from using plain text for identifiers, because it’s easy to mis-type…but if you’re generating all your identifiers, who cares?
  • Use function pointers as general-purpose selectors, instead of trying to support several types of limited selector. For example, instead of getElementById(id), getElementNamed(tagName), and a hypothetical getElementWithAttribute(attrName, attrVal), why not just getElement(evalFunction)?
  • Two of these ideas made the assumption that your HTML is organized a certain way, which isn’t always possible. If you have a page with lots of formatting (those pesky web designers), see if you can cordon off a section of clean HTML — just a div with an id — and only scan those nodes. Another reason to use getElements() instead of the globally-scoped methods the browser provides.

Use these techniques to come up with new and exciting ways to bend the browser’s DOM to your will. Muahahahaha.

For more info:
JavaDoc-style JavaScript, pretty browser-independent
Gecko DOM reference for Firefox
AJAX, DOM Hacking’s most typical setting