How to traverse tree-like structures recursively?

[pkolaczk]

The docs say:

A note about object safety: It is currently not possible to wrap a ParallelIterator (or any trait that depends on it) using a Box or other kind of dynamic allocation, because ParallelIterator is not object-safe. (This keeps the implementation simpler and allows extra optimizations.)

This basically rules out recursive transformation of parallel iterators. Cannot call a recursive function returning an impl ParallelIterator because it leads to recursive type, which is obviously not allowed. With standard iterators one can use Box<dyn Iter<...>> im such case but not with rayon.

What is the recommended way of doing recursion with rayon iterators?

How to implement this:

/// Return iterator over all items in a tree. 
fn traverse<I, Node, F>(root: Node, children: F) -> I
where 
  I: ParallelIterator<Item=Node>, 
  F: (Fn(Item) -> I) + Sync + Send,
  Node: Sync + Send

If it is complex to implement, could it be added as a new feature (probably with more options to determine traversal order)?

[bluss]

Nothing concrete, but for some trees, it might be possible to use rayon::iter::split

[cuviper]

Yeah, I think split could work for a tree, or at least it may be a good model of implementing an unindexed producer.

I've seen the Box<dyn Iterator> approach used before where it basically traverses the entire tree into an iterator tree, before the consumer gets to do anything at all. I really dislike that, because I feel like iterators ought to be as lazy as possible, and more so if you're hoping to parallelize it. Otherwise, you might as well collect that pre-traversal into a Vec, and then you can very quickly iterate that, in serial or parallel. Maybe you have a more dynamic approach though...

[pkolaczk]

I realized that the question is quite general and applies not only to trees. Another example could be chaining multiple iterators, where we don't know the number of input iterators statically.