Javascript: How to iterate on array using promises?

Question

LIVE DEMO

Given the following function:

function isGood(number) {
  var defer = $q.defer();

  $timeout(function() {
    if (<some condition on number>) {
      defer.resolve();
    } else {
      defer.reject();
    }
  }, 100);

  return defer.promise;
}

and an array of numbers (e.g. [3, 9, 17, 26, 89]), I would like to find the first "good" number. I would like to be able to do this:

var arr = [3, 9, 17, 26, 89];

findGoodNumber(arr).then(function(goodNumber) {
  console.log('Good number found: ' + goodNumber);
}, function() {
  console.log('No good numbers found');
});

Here is one possible recursive version to implement this: DEMO

function findGoodNumber(numbers) {
  var defer = $q.defer();

  if (numbers.length === 0) {
    defer.reject();
  } else {
    var num = numbers.shift();

    isGood(num).then(function() {
      defer.resolve(num);
    }, function() {
      findGoodNumber(numbers).then(defer.resolve, defer.reject)
    });
  }

  return defer.promise;
}

I wonder if there is a better (maybe non-recursive) way?

Humorous

Well, since you are only interested in the first good number, your approach seems fine, otherwise an implementation using q.all would have been more appropriate. However, shift is expensive so I would consider not mutating the array and simply increment an index. Nothing in the function's name implies that numbers will be mutated, so if you stick with that solution, at least make a copy of it with numbers.slice(). If you have many numbers (enough to fill the call stack), then go for an iterative approach using a stack. – Icbm

Is it important that you check each number before you check the next one, or is it allowed to check them all at once to find the first one that is good as fast as possible ? – Excision

What you have is close to the best solution if you forbid iterating the array in advance, if you can iterate the array (but not check it) in advance this can be simplified to a for loop. – Peabody

@Misha Moroshko can isGood function resolve with the number which he received ? – Vespers

Answer 1

I wonder if there is a better way?

Yes. Avoid the deferred antipattern!

function isGood(number) {
  return $timeout(function() {
    if (<some condition on number>) {
      return number; // Resolve with the number, simplifies code below
    } else {
      throw new Error("…");
    }
  }, 100);
}
function findGoodNumber(numbers) {
  if (numbers.length === 0) {
    return $q.reject();
  } else {
    return isGood(numbers.shift()).catch(function() {
      return findGoodNumber(numbers);
    });
  }
}

maybe non-recursive?

You can formulate a loop that chains lots of then calls, however recursion is absolutely fine here. If you really wanted the loop, it might look like this:

function findGoodNumber(numbers) {
  return numbers.reduce(function(previousFinds, num) {
    return previousFinds.catch(function() {
      return isGood(num);
    });
  }, $q.reject());
}

This is however less efficient, as it always looks at all numbers. The "recursive" version will evaluate it lazily, and only do another iteration if the current number was not good.

maybe faster?

You can fire all isGood checks in parallel, and wait for the first fulfilled to return. Depending on what isGood actually does and how well that is parallelizable, this might be "better". It potentially does a lot of unnecessary work, though; you may want to use a promise library that supports cancellation.

An example using the Bluebird library, which has a any helper function dedicated to this task:

function findGoodNumber(numbers) {
  return Bluebird.any(numbers.map(isGood))
}

Charlie

It would be nice not to slice the array n times, also it's fine to use .catch instead of .then(null, because it's Angular. – Peabody

The non recursive solution iterates the entire array though every time. – Peabody

@BenjaminGruenbaum: Added. The slicing was done delibaretely, I'm coming from a functional background and hate modifying my input :-) – Charlie

@Charlie Thanks for your answer. Just one thing: in the recursive version it should be return findGoodNumber(numbers); instead of findGoodNumber(numbers);. – Humorous

Answer 2

Here is an alternative solution with a different form of recursion:

function firstGood(arr){
    var i = 0;
    return $q.when().then(function consume(){
        if(i >= arr.length) return $q.reject(Error("No Number Found"));
        return isGood(arr[i++]).catch(consume);
    });
}

It's pretty similar to what Bergi has and it's about the best you can get without implementing a Promise.reduce like some libraries (Bluebird and more recently When) have.

Peabody

You should avoid the first isGood(arr[i++]).catch( and use a named IIFE instead, otherwise it won't work for empty arrays. – Charlie

@Charlie yeah, I fixed it into starting with an empty promise which is probably nicer anyway :) – Peabody

Answer 3

this is my version by simply using array.map function

Demo

angular.module('MyApp', []).run(function($q, $timeout) {
  var arr = [3, 9, 17, 26, 89];

  findGoodNumber(arr).then(function(goodNumber) {
    console.log('Good number found: ' + goodNumber);
  }, function() {
    console.log('No good numbers found');
  });

  function findGoodNumber(numbers) {
    var defer = $q.defer();

    numbers.forEach(function(num){      
      isGood(num).then(function(){
        defer.resolve(num);
      });

    });

    return defer.promise;
  }

  function isGood(number) {
    var defer = $q.defer();

    $timeout(function() {
      if (number % 2 === 0) {
        defer.resolve();
      } else {
        defer.reject();
      }
    }, 1000);

    return defer.promise;
  }
});

Vespers

What's the purpose of using map here? If you don't need the result array (of undefineds?), you should use .forEach or a simple loop. – Charlie

Answer 4

Promises were never meant to be used as booleans but that's effectively what isGood() is doing. And here, we don't just mean resolving/rejecting a promise with a boolean value. We mean that the state of a promise conveys its state :

• pending == as yet unknown
• resolved == true
• rejected == false

Some might regard this as promise abuse, but it's good fun trying to exploit promises in this way.

Arguably the main issues concerning promises as booleans are :

• The promise representation of 'true' will take the success path and the promise representation of 'false' will take the fail path
• Promise libraries don't naturally allow for all the necessary boolean algebra - eg. NOT, AND, OR, XOR

Until this topic is better explored and documented, it will take imagination to overcome/exploit these features.

Let's try and solve the problem (with jQuery - I know it much better).

First let's write a more definite version of isGood() :

/*
 * A function that determines whether a number is an integer or not
 * and returns a resolved/rejected promise accordingly.
 * In both cases, the promise is resolved/rejected with the original number.
 */ 
function isGood(number) {
    return $.Deferred(function(dfrd) {
        if(parseInt(number, 10) == number) {
            setTimeout(function() { dfrd.resolve(number); }, 100);//"true"
        } else {
            setTimeout(function() { dfrd.reject(number); }, 100);//"false"
        }
    }).promise();
}

We are going to need a "NOT" method - something that swaps 'resolved' and 'rejected'. jQuery promises don't have a native inverter, so here's a function to do the job.

/* 
 * A function that creates and returns a new promise 
 * whose resolved/rejected state is the inverse of the original promise,
 * and which conveys the original promise's value.
 */ 
function invertPromise(p) {
    return $.Deferred(function(dfrd) {
        p.then(dfrd.reject, dfrd.resolve);
    });
}

Now, a version of the question's findGoodNumber(), but here exploiting the rewritten isGood() and the invertPromise() utility.

/*
 * A function that accepts an array of numbers, scans them,
 * and returns a resolved promise for the first "good" number,
 * or a rejected promise if no "good" numbers are present.
 */ 
function findGoodNumber(numbers) {
    if(numbers.length === 0) {
        return $.Deferred.reject().promise();
    } else {
        return invertPromise(numbers.reduce(function(p, num) {
            return p.then(function() {
                return invertPromise(isGood(num));
            });
        }, $.when()));
    }
}

And finally, the same calling routine (with slightly different data) :

var arr = [3.1, 9.6, 17.0, 26.9, 89];
findGoodNumber(arr).then(function(goodNumber) {
    console.log('Good number found: ' + goodNumber);
}, function() {
    console.log('No good numbers found');
});

DEMO

It should be quite simple to convert the code back to Angular/$q.

Explanation

The else clause of findGoodNumber() is maybe less than obvious. The core of it is numbers.reduce(...), which builds a .then() chain - effectively an asychronous scan of the numbers array. This is a familiar async pattern.

In the absence of the two inversions, the array would be scanned until the first bad number was found and the resulting rejection would take the failure path (skipping the remainder of the scan and proceeding to the fail handler).

However, we want to find the first good number to take the "failure" path- hence the need for :

• the inner inversion: to convert reported "true" to "false" - forcing the rest of the scan to be skipped
• the outer inversion: to restore the original bloolean sense - "true" ends up as "true" and "false" ends up as "false".

You may need to mess around with the demo to better appreciate what's going on.

Conclusion

Yes, it's possible to solve the problem without recursion.

This solution is neither the simplest nor the most efficient, however it hopefully demonstrates the potential of promises' state to represent booleans and to implement asynchronous boolean algebra.

Alternative solution

findGoodNumber() can be written without needing to invert by performing an "OR-scan", as follows :

function findGoodNumber(numbers) {
    if(numbers.length === 0) {
        return $.Deferred.reject().promise();
    } else {
        return numbers.reduce(function(p, num) {
            return p.then(null, function() {
                return isGood(num);
            });
        }, $.Deferred().reject());
    }
}

This is the jQuery equivalent of Bergi's solution.

DEMO

Bottali

Why do you use not(AND[promises.map(not)])? You simply could do OR[promises] by using then's error handler to chain. – Charlie

@Bergi, yes it's just like regular boolean logic. There's more than one way to skin the cat. My imagination led me in one direction, yours led you in another. – Bottali