Sunday, February 23, 2014

Bird Watching with JavaScript -- The Bluebird

"The first sparrow of spring! The year beginning with younger hope than ever! The faint silvery warblings heard over the partially bare and moist fields from the bluebird, the song sparrow, and the red-wing, as if the last flakes of winter tinkled as they fell! What at such a time are histories, chronologies, traditions, and all written revelations? The brooks sing carols and glees to the spring."
-- Henry David Thoreau
Walden, page 160

The Open Woodlands


Music all around.  A slight breeze is gently rustling the grass and leaves.  The song of the bluebird fills the air.  You call out X.  It sings back X.  You call out Y.  It sings back Y and X.  You call out Z.  It sings back Z, Y, and X.

The Bluebird




One of the first higher order functions that people learn is the composite function.


In combinatory logic the composite function is known as the B combinator.

B f g x = f (g x)

It also goes by the name given to it in To Mock a Mocking Bird, the bluebird.

Compose in Haskell


One of the things I love about Haskell is that if you look at a method signature you can pretty much tell what the function does.

Here is the definition of the compose function taken from the Haskell source.

(.)    :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)



Looking at the definition we see that we need two functions, one goes from b to c and the other goes from a to b.  When given the value a the output is value c.

Looking at the actual function we see we have f (g x).  Meaning take the 2nd function I gave you (a -> b) and apply that to the argument a that I gave you.  Now take the result of (a -> b) and apply the 1st function I gave you (b -> c) against that.  The result of applying the (b -> c) function is the result I want returned.

Compose in Underscore


We see that compose is built into Haskell but what about JavaScript?  Reading Reginald Braithwaite's excellent book JavaScript AllongĂ© we see a definition of compose but we do find anything built into JavaScript (reading this book is what prompted me to write this post).  Luckily Underscore.js has us covered!

_.compose(*functions) 

Looking at the functional definition we see that we can pass in any number of functions and have compose create a function which applies all of them to the argument given to it.

  _.compose = function() {
    var funcs = arguments;
    return function() {
      var args = arguments;
      for (var i = funcs.length - 1; i >= 0; i--) {
        args = [funcs[i].apply(this, args)];
      }
      return args[0];
    };
  };

In fact looking at the annotation source we see that it applies all of the function we give it to how ever many arguments we give it!

Characterization Test of Underscore's compose



it("Given a bunch of identity functions it will return the value given", function(){
var ids = _.compose(_.identity, _.identity, _.identity, _.identity);
expect(ids("Mike Harris")).to.be.equal("Mike Harris");
})

We verify that we can apply compose however many times we wish to the identity function, which is also known as the I combinatory or the idiot bird, and we will get the same value back, f(x) = x.

it("Given an increment function it will return one more", function(){
var plus1 = _.compose(increment);
expect(plus1(42)).to.be.equal(43);
})

We see we can also pass in only one function and have that function applied to the argument we give it.

it("Given a absolute value and square root functions but used in the wrong order " +
"we cannot find positive square roots", function(){
var wrongPosSqrt = _.compose(Math.abs, Math.sqrt);
expect(_.isNaN(wrongPosSqrt(-4))).to.be.ok();
// even better
var failedPosSqrt = _.compose(_.isNaN, wrongPosSqrt);
expect(failedPosSqrt(-4)).to.be.ok();
// or
var showWhenFailed = _.compose(function(x){return !x;}, failedPosSqrt);
expect(showWhenFailed(2)).to.be.ok();
expect(showWhenFailed(-2)).to.not.be.ok();
})

We also verify that the order does matter.  When we use compose we need to think of it as applying the functions given in the order that we would read it if we wrote it out.

function wrongPosSqrt (x) = {return Math.abs(Math.sqrt(x));};

is very different from

function posSqrt (x) = {return Math.sqrt(Math.abs(x));};

The End


The bluebird can be thought of as a gateway to the larger world of functional programming.  With the simple concept of applying function together we see that we can built up simple existing functions to larger more complex functions.  This is one of the core concepts of functional programming.