Tuesday, October 2, 2012

Higher Order Functions

Javascript treats functions as first class values meaning functions can be passed as parameters and returned as results.
Higher order functions are functions that take other functions as parameters and/or return a function as a result.

You can try the examples in this post by cutting and pasting code here.


Passing functions as params

Lets say we want a way of summing different things - integers, squares, factorials etc. We can break this problem into:


1. The summing algorithm (pseudo code)

 sum(f, lower, upper) - >  
   summingLoop(lower, accumlator) ->  
     if(lower > upper) 0  
     else summingLoop(lower + 1, f(lower) + accumlator)  
   summingLoop(lower, 0)  


2. The thing to be summed


 square(x) -> x * x  

A Javascript implementation of this might look like the following.

The summing part:


1:   var sum = function(fun, a, b) {  
2:    var loop = function(a, acc) {    
3:     if(a > b) return acc  
4:     else return loop(a + 1, fun(a) + acc)  
5:    };  
6:    return loop(a, 0);  
7:  };  

Applying the thing to be summed: 

Calculate the sum of squares between 3 and 5.
 writeln('sum of squares 3 .. 5: ' + sum(function(x){return x*x;}, 3, 5));  

With the higher order summing function we can easily sum factorials between 3 and 5:

1:  var factorial = function(n) {  
2:        var loop = function(acc, n) {  
3:             if(n == 0) return acc;  
4:             else return loop(acc * n, n - 1);  
5:       };  
6:        return loop(1, n);  
7:   };   

So now we can sum factorials between upper and lower bounds like so:


 // sum of factorials in range 3 .. 5: 150  
 writeln('sum of factorials in range 3 .. 5: ' + sum(factorial, 3, 5));  

Note: Higher order functions are a great application of DRY principle (Dont Repeat Yourself)

Functions that return a function

Taking our previous summing example, we'll modify it to return a function as a result.

  var sum = function(fun) {   
     return function(a, b) {  
       if(a > b) return 0;  
       else return fun(a) + sum(fun)(a + 1, b);  
    };  
  };  
 // sumOfSquares 3..5: 54  
 var sumSquares = sum(function(x){return x*x;})( 3, 5);  
 writeln('sumOfSquares 3..5: ' + sumSquares);  

Here, we've tightened our original implementation by isolating the injection of the function from the application of summing a range by returning the function that applies the summing over a range. In doing so, we've also managed to strip an extra line of code from the original implementation.

IMHO usage of the function has improved also. I now have more options to be expressive:

 // Expressed though inlining  
 sum(factorial)(3, 5);  
 //OR, broken down for increased expressiveness  
 var sumFactorialsOf = sum(factorial);  
 sumFactorialsOf(3, 5);  


A typical application of higher order function technique in the wild


Consider the following generic function, which takes a filter function and returns a new function, allowing you to apply the filter over an array of values.


1:  function filterBy(fn) {  
2:       return function(results) {  
3:            var filtered = [];  
4:            results = results || [];  
5:            results.forEach(function(number) {  
6:                 if(fn.apply(null, [number])){ filtered.push(number); }  
7:            });  
8:            return filtered;  
9:       };  
10:  }  

We'll also need a filter algorithm to allow our generic filter function to specifically return all even numbers in an array.


1:  function evens(number) {   
2:         return number === 0 ? false : number % 2 === 0;  
3:  }  

Let's apply this function to the task at hand: filter out anything that is not an even number in an array of values.


1:  function printResultsFor(evaluated) {  
2:         writeln('event numbers are: [' + evaluated + ']');  
3:  }  
4:    
5:  var evenFilter = filterBy(evens);  
6:    
7:  printResultsFor(evenFilter(['one', 'tu',7,8,0])); //  event numbers are: [8]  
8:  printResultsFor(evenFilter([1,3,6,7,8,0])); //  event numbers are: [6,8]  
9:  printResultsFor(evenFilter([1,3,7,9,0])); //  event numbers are: []  
10: printResultsFor(evenFilter()); //  event numbers are: []  


Closing

Generally speaking, higher order functions provide a powerful technique for reducing repetition (DRY).

They should be considered when you find yourself calling the same function and passing mostly the same parameters. 

The programming technique of writing functions that take one or more functions and return a function is also known as currying.

Javascript implementations provide a host of higher order functions: Array.forEach,  map, fold or reduce, filter, compose, partial, and others.


Further Reading