Create in-order, post-order, pre-order versions of `walk()`.

[atdixon]

In many cases it is useful/essential to rely on predictable tree traversal order.

DFS variants include in-order, post-order, pre-order [1]; BFS is knowns as level-order.

The current contract of walk() is arbitrary-order, although it appears to be doing a reverse of post-order.

[1] https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search

[lukasbuenger]

Hi Aaron, thanks for your feedback.

Currently walk does a reverse of post-order. The reason why it's documented as arbitrary is so that people will not rely on any specific order, which makes it easier to tweak and maintain the innards of walk without breaking any expectations on the result. That was the idea anyway. I also rejected a similar ticket some time ago https://github.com/lukasbuenger/immutable-treeutils/issues/7.

That being said, I'm open to having a selection of tree traversal methods, as any performance impacts will probably be neglected by the fact, that clients will likely query more efficiently due to predictable traversal behavior.

Let me think on this for a while and I'll get back to you.

[atdixon]

Thanks for the reply. Another consideration when revisiting the walk API is to have an optional initial value for the reduction — which I think is fairly idiomatic across functional languages. (e.g., initialValue in https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce). Thanks much for this library.

[lukasbuenger]

@atdixon

Hi Aaron, I just wanted to give you a short update on this. First of all, I was wrong in that the current algo does a reverse pre-order and not a post-order. Sorry for that. The good news is, that I've pretty much finished the feature already. I'm still figuring out the exact API but I think I will be able to release this by the end of this month.

[atdixon]

Superb—I will keep an eye on this. Thank you!