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);
| ^^^^^^^^^^^^^^^^^^^^^^^^^
|
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
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.
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
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