Iteration: internal vs external vs generation?

help
1

I have a tree of different types of objects, all of which implement a trait Widget. At times I need a way to walk the tree, so one of the methods I defined on the trait was:

pub type WidgetChildIter<'a> = 
    Box<dyn DoubleEndedIterator<Item = Rc<dyn Widget + 'static>> + 'a>;
fn iter_children(&self) -> Option<WidgetChildIter<'_>> { None }

It’s proving difficult to implement this. The different Widget types tend to have different internal structure and the iteration is a combination of if/else and sub-loops. So I thought it might be easier to do an “internal” iterator, like this:

impl Widget for Thingy {
    fn iter_children(&self, f: Box<dyn Fn(&dyn Widget)>) {
        if let Some(br) = self.border_rectangle { f(br) }
        for w in self.components { f(w) }
        ...

It seems easier to write, and read, but it doesn’t seem to be the usual Rust way to iterate. Is the main downside that I then miss out on all the things implemented for Iterator, like the map/filter/zip/etc?

I could add some parameters for reverse direction or stopping early.

From what I can tell a “generator” would combine the best of both worlds, but that is not in stable Rust yet. ?

Any recommendations?

2

Check out https://doc.rust-lang.org/std/ops/enum.ControlFlow.html#examples -- ControlFlow works with ? as a good way to handle early returns from things like this.

2 Likes
3

This blog post describes the situation pretty well, but here's a shorter summary:

While map and filter are basically just convenience functions, the important one is zip, which allows you to iterate over two separate data structures in lockstep. With callback-based internal iteration, this is impossible in Rust:

let first = [1, 2, 3];
let second = [4, 5, 6];
// using zip
for (n1, n2) in first.iter().zip(second.iter()) {
    println!("{n1} {n2}"); // 1 4 \n 2 5 \n 3 6 \n
}
// by hand
let mut first_iter = first.iter();
let mut second_iter = second.iter();
loop {
    let Some(n1) = first_iter.next() else { break };
    let Some(n2) = second_iter.next() else { break };
    println!("{n1} {n2}"); // 1 4 \n 2 5 \n 3 6 \n
}

You could rewrite the entire iteration logic as a bespoke iterate_children_on_two_thingies(self: &Thingy, other: &Thingy, f: Box<dyn Fn(&dyn Widget, &dyn Widget)>), but you can't use iter_children(self: &Thingy, f: Box<dyn Fn(&dyn Widget)>) to implement it. You also can't use iterate_children_on_two_thingies to iterate over three thingies.

4 Likes