Recursive tree navigation with callback

help
#1

Is it possible to make the following for_each implementation work?

struct Tree {
    pub children: Vec<Tree>,
    pub data: i32,
}

impl Tree {
    pub fn for_each(&self, callback: impl Fn(i32)) {
        callback(self.data);

        for child in &self.children {
            child.for_each(&callback);
        }
    }
}

I've tried invoking it with both a closure and a function, but both cause recursion problems.

fn main() {
    let tree = Tree {
        children: vec!(),
        data: 0x1,
    };
    
    // Attempt 1
    tree.for_each(|x| println!("{}", x));
    
    // Attempt 2
    fn callback(x: i32) {
        println!("{}", x);
    }

    tree.for_each(callback);
}

This is the error, in any case:

error: reached the recursion limit while instantiating `Tree::for_each::<&&&&&&&&&&&&&&&...osure@src/main.rs:27:19: 27:40]>`
  --> src/main.rs:15:13
   |
15 |             child.for_each(&callback);
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^
   |
#2

Does it work if you define for_each like so?

    pub fn for_each(&self, callback: &impl Fn(i32)) {
        callback(self.data);

        for child in &self.children {
            child.for_each(callback);
        }
    }

I think, because the recursive call uses &callback, it needs to instantiate a trait implementation for all the recursive references, I think with my adjustment it should be able to unify them.

1 Like
#3

Hey, this works. Now invoking it like:

// Attempt 1
tree.for_each(&|x| println!("{}", x));

// Attempt 2
fn callback(x: i32) {
    println!("{}", x);
}

tree.for_each(&callback);

I think, because the recursive call uses &callback, it needs to instantiate a trait implementation for all the recursive references

Can you elaborate on this? It seems to me now that &callback never made sense to provide to impl Fn(i32) to begin with (a reference to a non-reference...?), although it doesn't seem to matter for a non-recursive example.

impl Tree {
    // Just to demonstrate
    pub fn for_root(&self, callback: impl Fn(i32)) {
        callback(self.data);
    }
}

fn main() {
    let tree = Tree {
        children: vec!(),
        data: 0x1,
    };

    // Both of these work
    tree.for_root( |x| println!("{}", x));
    tree.for_root(&|x| println!("{}", x));
}

I think I just don't understand traits too well or what they're doing here.

#4

You may wish to hide this detail with an internal function, so that callers need not take a reference.

Presumably you tried passing a shared reference inside the function because otherwise you get an error about moving the closure. The disconnect is that the parameter is opaque (it can be anything that implements Fn(i32)), and if F implements Fn(i32), so does &F. "impl F(i32)" can't see through the generics to act differently when you pass it a reference or not, so the type of the parameter becomes recursive:

  • F when you call it from main
  • &F when you call it from for_each at the first level
  • &&F when you call it from for_each at the second level
  • Etc.

But when you use &impl Fn(i32) instead, you just copy the same shared reference around everywhere (because &T implements Copy for any T). The parameter is now expecting a reference instead of some opaque Fn(i32) implementor.

Another alternative would be to move the callback everywhere by returning it from for_each, but that looks less clean IMO.

5 Likes
#5

A further improvement beyond what @quinedot suggested would be to use a (more typical for a non-parallelized “for_each” method, and also more general) FnMut bound instead of Fn, together with &mut in place of &: Rust Playground

2 Likes