Compose & Sequence created using recursion & imperative

Introduction

As I’m making my way further down the rabbit hole of the functional programming paradigm, I have found myself at the topic of recursion and wanted to do a post demonstrating how we can take an imperative operation and turn it into a recursive one but also using a real world example of something useful, hence why I decided that implementing compose & sequence[1] would be a good demonstration, first let’s get acquainted with these 2 functions.

Brief Introduction to Compose & Sequence

In functional programming you typically end up with functions calling other functions that then may also be called by another function[2], so if we had functions a, b and wanted to join them into a function called c:

var c = a(b);

This becomes harder to read as we have more nested calls, ideally we would like to pass the results of one function into another this is where compose and sequence come in, compose works from right to left and sequence left to right:

var c = compose(b, a);
// or
var c = sequence(a, b);

Typically compose is used as a function that takes 2 functions like the above in which case the implementation is trivial:

var compose = function (a, b) {
  return function () {
    return a(b.apply(b, arguments));  
  };
};

It returns a closure and applies on the second function using the arguments passed in and then uses the result of this call to pass to the first function and return the results. We can execute like this:

var print = function (val) { console.log(val); };
var double = function (val) { return val * 2; };

var display = compose(print, double);
display(10);

However in JS we can do much better than this because of its varargs support via the special arguments variable[3] so what I want to do next is go through how we can implement the compose & sequence functions using both an imperative approach or by using recursion.

Imperative Approach

First let’s start by creating the sequence function:

var sequence = function (/* funs */) {
  var funs = Array.prototype.slice.call(arguments);
  var len = funs.length;
     
  return function (/* args */) {  
    var args = funs[0].apply(funs[0], arguments);
    for (var i=1; i < len; i++) {
      args = funs[i](args); 
    }
        
    return args;
  };
};
  1. The sequence function does not specify the arguments explicitly as instead we are going to take multiple functions[4]
  2. The functions supplied are extracted from the arguments variable
  3. A closure is then declared that will be returned to the caller
  4. The argumentsfrom this closure are then used to call the first function supplied
  5. The results of this function call are stored in args variable
  6. The remaining functions passed are then called using a for loop each time the args variable is being mutated to contain the results of each function call
  7. Once the functions have all been executed the value stored in args is returned

The only difference between compose and sequence is that compose runs from right to left so if we can take all the existing code and just make this one bit of behaviour configurable we will save ourselves having to duplicate code:

var stitch = function (reverse) {
  return function (/* funs */) {
    var funs = Array.prototype.slice.call(arguments);
    var len = funs.length;
    
    if (reverse) funs.reverse();
    
    return function (/* args */) {  
      var args = funs[0].apply(funs[0], arguments);
      for (var i=1; i < len; i++) {
        args = funs[i](args); 
      }
    
      return args;
    };
  };  
};

This uses much of the same code as before but this function now takes a reverse boolean that when set to true will perform a reverse on the functions passed in[5], and returns another closure (to take advantage of partial application[6]), we can now implement compose & sequence using this new function:

var compose = stitch(true);
var sequence = stitch(false);

Recursive Approach

In order to understand recursion, you must understand recursion

- Hunter, David (2011)

One section mentioned in Functional Javascript regarding recursion was the rules of thumb (Touretzky 1990) for every recursive function:

  • Know when to stop
  • Decide how to take one step
  • Break the problem into that step and a smaller problem

I will show how each relates to the recursive function of sequence & compose, now first let’s create a sequence function:

var sequence = function (/* funs */) {
  var funs = Array.prototype.slice.call(arguments);
  var recurse = function recurse(funs/*, args */) {
    var args = Array.prototype.slice.call(arguments, 1);  
    if (_.isEmpty(funs))
      return args;
        
      var fun = _.first(funs);
      recurse(_.rest(funs), fun.apply(fun, args));
  };
    
  return recurse.bind(null, funs);
};

First thing to note is that I’m taking advantage of underscore.js[7] this takes away a lot of the menial work.

  1. Like the imperative version we are taking any number of functions so we use the arguments variable to capture the arguments
  2. Next we declare an internal function called recurse, this is the function that will perform the recursion, this function accepts the array of functions as it’s first argument to make it more explicit about what it takes
  3. It first pulls out the arguments supplied, ignoring the first element because this will be the array functions
  4. A check is performed to see if we have removed all the functions from the array, if this is the case we return arguments that were passed in from the last call
  5. Otherwise we use the _.first function which as you might guess returns the first element when passed an array
  6. The we call ourselves, the first parameter we use _.rest which returns an array with the first element removed (we captured this above). The next parameter is calling the current function using the arguments we were supplied.
  7. It then returns a partially applied function[8] bound to the recurse function with the captured functions so it is ready to be executed by the caller

This can then be used in the same way as the imperative version:

var print = function (val) { console.log(val); };
var double = function (val) { return val * 2; };

var display = sequence(print, double);
display(10);

Here is a diagram to help illustrate how the recurse function works using the example above:

And so how does this fit in with the recursion rules of thumb I mentioned previously:

When to stop
_.isEmpty(funs)
Take one step
recurse(_.first(funs)…
Smaller problem
recurse(_rest.(funs)…

One thing to note is that this recursive function is written to enable tail recursion[9] however JS does not have support for this unlike full functional programming languages such as Scheme.

The next step is to enable compose, we can do this by abstracting the order in which the functions are picked:

var stitch = function (take, remove) {
  return function (/* funs */) {
    var funs = Array.prototype.slice.call(arguments);
    var recurse = function recurse(funs/*, args */) {
      var args = Array.prototype.slice.call(arguments, 1);  
      if (_.isEmpty(funs))
        return args;
        
        var fun = take(funs);
        recurse(remove(funs), fun.apply(fun, args));
    };
            
    return recurse.bind(null, funs);
  };
};

Similar to the imperative version we have created a new function called stitch, only this time we accept 2 functions one that will decide how to take a function from the array and another that will decide how to remove a function from the array, now using our good friend partial application we can declare both sequence and compose:

var compose = stitch(_.last, _.initial);
var sequence = stitch(_.first, _.rest);

The compose simply passes _.last (retrieves the last element when passed an array) and _.initial (returns a new array with the last element removed).

Summary

I have demonstrated a couple of ways of how these 2 functions can be implemented there are a whole host of other ways they could be implemented (or you could just use _.compose!) hopefully this will be helpful at this post has certainly helped me get a better understanding of how to apply recursion.


  1. Also known as pipeline in other languages
  2. Functional Composition
  3. The arguments variable
  4. I like to add a comment in the function parentheses to denote the arguments we are expecting just to make it clearer that we are expecting arguments (a handy trick picked up from Functional Javascript)
  5. I know from a micro performance point of view this isn’t as efficient as looping backwards but we are talking a tiny amount of functions that are going to be passed in so I don’t think this is going to be the bottleneck of your application.
  6. You could also change the signature to be function (reverse, /* funs */) and then use bind var compose = stitch.bind(null, true); but I think this nicely separates the configurable part from the actual usage part.
  7. This is JS library that provides functional style functions such as map, reduce etc… just a shame about the argument ordering as it means partial application cannot be applied out of the box.
  8. For more info partial application check out this post
  9. Tail Recursion
About these ads

One thought on “Compose & Sequence created using recursion & imperative

  1. Pingback: Functional Programming & DSL’s Part 2 | Journal of a software dev

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s