JavaScript Promises: Recursively Building Promise Chain With Breadth-First Traversal

Question

Native Javascript ES5/ES6 Promises

I'm trying to import data that has a recursive relationship and since the database(mongodb) is assigning ids - a parent has to be loaded(asynchrnously) before it's children can be loaded(also async).

For example, Task B in this list of tasks.

Task A - Some Process

Task B - Recursive Async Loading(bread-first traverse)

Task C - Dependent on Task B

Notice since Task C can't be started until Task B is complete I assume a promise chain will need to be built that doesn't exit until it is done.

The assume the chain being built would look something like this: (the tree has only 1 head)

promiseParent.then(Promise.all(childrenPromises.then(Promise.all(grandChildrenPromsies.then(....)))))

I imagine it would traverse like a breadth-first queue (preferable I would like to try to avoid using a queue data structure if it's possible)

I found this one to be a tough one to crack. Any suggestions or solutions?

Wouldn't you just chain it? `taskA.then(function() { return taskB() }).then(...` — adeneo, Mar 09 '16 at 00:52
Task B is the challenge. Task B needs to recursively build a chain of promises to complete before Task C is called. Task A is irrelevant (just shows stuff happens before B is called. @BlakesSeven — Nick Pineda, Mar 09 '16 at 00:56
I didn't make the comment. @adeneo did. All I did was remove the mongodb tag ( presumably automatically inserted by the magical stackexchange question editor ! ) since it really doesn't relate specifically to a problem all about promises. — Blakes Seven, Mar 09 '16 at 00:58
Noticed but too late, sorry Blake - and yea, it's not too relevant to the Mongodb community I guess. — Nick Pineda, Mar 09 '16 at 01:01
My point being, you don't have to nest them, you can chain them — adeneo, Mar 09 '16 at 01:02
Chaining the tasks inside Task B is the goal though. I hope people aren't thrown off by Task A being in the example. — Nick Pineda, Mar 09 '16 at 01:04
Could you use [Promise.all()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise/all) in Task B? — Jesse Kernaghan, Mar 09 '16 at 01:05
Aren't you just trying to do something like this -> **https://jsfiddle.net/60h2vv3e/** — adeneo, Mar 09 '16 at 01:06
I don't see how you would write a [breadth-first traversal](https://en.wikipedia.org/wiki/Breadth-first_search) without a queue. [Looping](http://stackoverflow.com/a/29396005/1048572) until that is empty is trivial. — Bergi, Mar 09 '16 at 01:13
@JesseKernaghan I couldn't figure out how to return the promise of children before the promise of their parent was completed. Because I couldn't call for the children to be made because they saved a link to their parent by having a property that stored the parentID. — Nick Pineda, Mar 09 '16 at 01:13
@adeneo - close to that, but their needs to be a recursive call that loads the children once the parent is done. — Nick Pineda, Mar 09 '16 at 01:16
@Bergi if a queue is necessary I'll use it - I was just hoping that the promise chain and the recursive stopping once it hit the a child with no children could work without a queue data structure. — Nick Pineda, Mar 09 '16 at 01:18
@NickPineda: A queue is necessary for breadth-first traversal. If you are fine with concurrent loading (parallel traversal), you don't need one. See [these links](http://stackoverflow.com/a/22911399/1048572) for examples of how to do that. — Bergi, Mar 09 '16 at 01:21
Do you know the number of children ahead of time? If yes, then you should not need to recurse. — jib, Mar 09 '16 at 06:01

score 2 · Accepted Answer · edited May 23 '17 at 11:59

Promise chains can be extended dynamically, with new links inserted at any point in a chain, simply by returning a promise from any .then fulfillment handler.

Say each Task resolves with an array of its children. If children can be processed in parallel, then:

promiseParent
.then(children => Promise.all(children.map(child => loadChild(child))))
.then(grandchildren => Promise.all(grandchildren.map(child => loadChild(child))))

should do. If children must be processed sequentially, then:

let sequence = (a, f) => a.reduce((p, c) => p.then(() => f(c)), Promise.resolve());

promiseParent
.then(kids => sequence(kids, kid => loadChild(kid)).then(() => nextGen())
.then(gkds => sequence(gkds, kid => loadChild(kid)).then(() => nextGen())

will do that (I'm simplifying by assuming nextGen knows to return the next generation).

If the number of children must be discovered recursively, then:

let loadChildrenRecursively = child => loadChild(child)
  .then(nextChild => nextChild && loadChildrenRecursively(nextChild));

promiseParent
.then(firstChild => loadChildrenRecursively(firstChild)).then(() => nextGen())
.then(firstGchild => loadChildrenRecursively(firstGchild)).then(() => nextGen())

should do that.

To generalize this to N levels, pick any approach above, say in parallel, and recurse on it:

let doGeneration = generation =>
  Promise.all(generation.map(child => loadChild(child))))
  .then(offsprings => offsprings && doGeneration(offsprings))

promiseParent.then(children => doGeneration(children));

So you can always extend as long as there is more to do, by resolving a promise with another promise (which is what you implicitly do by returning a new promise from a .then fulfillment handler).

@Bergi I've updated the answer to cover a dynamic number of levels as well. — jib, Mar 09 '16 at 07:30
@jib Holy!! Wow that answer looks slick! Yea I was hoping for a dynamic answer to allow flexibility in the branch depth( so thanks Bergi for adding that in there) and sequential since the child will need the new parent id before it too can be imported. — Nick Pineda, Mar 09 '16 at 10:42
Thanks! Btw, *in parallel* just means in parallel with other children, so all three solutions would presumably have access to a parent id, because they all wait for all parents to finish before starting. - Also, if parent id is the only thing you're waiting for, then you might not strictly need Breadth-First Traversal, since you wouldn't need to wait for *sibling parents* I don't think, just your own parent? If you wanted to optimize, that is. — jib, Mar 09 '16 at 13:16

JavaScript Promises: Recursively Building Promise Chain With Breadth-First Traversal

1 Answers1