Nodejitsu

Save time managing and deploying your node.js app. Code faster with jitsu and npm

Pattern Matching in Javascript for Asynchronous Iteration

About the author

Name
Location
Worldwide
nodejitsu nodejitsu

pattern (github, p on npm) is a way to iterate javascript collections with asynchronous functions using a technique called pattern matching.

Asynchronous functions

An asynchronous function is one that usually returns before having finished its job and takes a function it should call when the job is done. that action is the callback, a function to be executed at that point in time.

// async
var fs = require('fs');  
// callback
function logContents(err,contents) { console.log(contents); }  
var contents = fs.readFile('a.txt', 'utf8', logContents);  
console.log('1');  
// outputs 1, then the contents of the file when the file is read

vs.

// sync
var fs = require('fs');  
var contents = fs.readFileSync('a.txt', 'utf8');  
console.log(contents);  
console.log('1');  
// outputs the contents of the file, then 1.

Iterating in javascript with asynchronous functions

The problem

When someone is starting with node i always recommend they watch pedro teixeira's video nodetut on asynchronoys iteration patterns

In this nodetuts video Pedro shows how to iterate asynchronously in node.js. here is the naive approach code he shows which doesn't work:

// simulating an asynchronous call, e.g. getting something from a database
var asyncFn = function(data, callback) {  
  var timeout = Math.ceil(Math.random() * 3000);
  // run callback after timeout miliseconds
  setTimeout(function() { callback(null, data); }, timeout);
};

var insertAll = function(coll, callback) {  
  coll.forEach(function (nr) {
    asyncFn(nr, function(err,data) {
      console.log('‣', data);
    });
  });
  callback();
};

insertAll([1, 2], function() {  
  console.log('done'); });

This will not work as you probably think it does:

done  
‣ 1
‣ 2

The reason is that the insertAll function returns before the async function calls the callback so done gets logged before the function is complete.

Solving the problem with a module

If you think implementing your own asynchronous iteration function is too much hassle there's plenty of modules out there that solve this problem. my favorite is async.

In async the solution for this problem would be something like:

async.forEach([1, 2], asyncFn, function(err, results){  
   console.log('done');
});

To iterate is human, to recurse is divine

When looking to the solution to this problem without the help of a module it struct me as obvious how much all these algorithms work like pattern matching.

  • if the queue exists run some generic processing the queue function
  • if the queue is empty run the callback
queue execute
empty call back
has Elements iterate

What is pattern matching?

Pattern matching is a recursive way to develop your programs where you define patterns for the program to identify and match those patterns with actions that should be executed.

Let's consider the very well understood map function that takes a collection and transforms each element by applying a function:

[1,2,3].map(function duplicate(x) { return x*2; });

If you solved this problem using pattern matching the execution of this function would be:

transformed_map = [];  
map:  
  l = [1,2,3]
    is l an empty array?
      no.
    is l anything?
      yes.
      head = 1
      tail = [2,3]
      transformed_map.shift(duplicate(1));
      map([2,3])
transformed_map = [2];  
map:  
  l = [2,3]
    is l an empty array?
      no.
    is l anything?
      yes.
      head = 2
      tail = [3]
      transformed_map.shift(duplicate(2));
      map([3])
transformed_map = [2,4];  
map:  
  l = [3]
    is l an empty array?
      no.
    is l anything?
      yes.
      head = 3
      tail = []
      transformed_map.shift(duplicate(3));
      map([])
transformed_map = [2,4,6];  
map:  
  l = []
    is l an empty array?
      yes.
      return transformed_map
[2,4,6]

Solving the problem with pattern

I decided try to implement pattern matching in javascript as my js1k entry called functional love.

The rules were simple: implement functions that allow you to do pattern matching in javascript without changing the language itself.

This is what i came up to for the node tuts episode:

insert_all([], function done() { console.log('done'); });  
insert_all(_, function all(l) {  
  insert_element(l.shift(), function (err, elem) {
    console.log('‣ ', elem);
    insert_all(l);
  });
});
  • if the array is empty, log the message done.
  • if its not empty, insert the element and when the callback is complete recursively call the insert_all function with the rest of the list.

You can now call this function like this:

insert_all([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);  

How it works

You probably noticed i use the same syntax to declare the insert all function and to call the function itself. what happens is the first time you call pattern it sets the arity of the function. is this case the first pattern has two arguments, meaning i should expect a function with one argument. whenever i call insert_all with one argument i'm calling the function.

When you registered the first two patterns i created a fact table like:

list execute
empty done()
has elements all()

Now when you call the insert_all function we need to iterate this fact table and see which rule applies. then call that function. simple. if the function wants to recurse it simply need to invoke the insert_all function.

Mad science corner

Ok enough with the easy stuff. let's use pattern to implement a function that reverses an javascript array. asynchronously of course:

reverse([5,4,3,2,1], function (list) { console.error(list); });  

We can do this using the reduce function that takes a list l and an accumulator z and returns something that was constructed by applying a function f to each element of the list x and the accumulator z.

// pretending asynchronous behavior
// image this is some kind of echo server
function echo(z, x, cb) {  
  setTimeout(function() {
    z.unshift(x); cb(z);
  }, Math.ceil(Math.random() * 100)); 
}

function reverse (l, cb) { reduce(echo, [], l, function(z) { cb(z); }); }  

Now all we need is to implement the reduce function with pattern:

var _;  
reduce(_, _, [], _, function (f, z, l, cb) { cb(z); });  
reduce(_, _, _, _, function (f, z, l, cb) {  
  f(z, l.shift(), function (new_z) {
    reduce(f, new_z, l, cb);
  });
});

Get the full code for this example here.

Js1k

pattern is my js1k submission. it was a lot of fun to write. if you are wondering if you should submit an entry yourself you totally should.