Recursive function to apply a lambda to all elements of a tree

[John_Nagle]

Rust Playground

Here's a recursive function which traverses a tree, applying a provided lambda to each element.

The obvious implementation

fn apply(&self, func: impl FnMut(&TreeItem))

leads to compiler error messages and recommendations which are both confusing and sometimes wrong. Using "dyn" fixes the problem. Is that the best solution?

[quinedot]

&mut impl FnMut(..), aka <F: FnMut(..)>(_: &mut F), also works without dynamic dispatch.

You can also take impl FnMut(..) by value on the public method and pass a &mut impl _ to a private method.

(Sorry for the brevity; on mobile. I can elaborate later if needed.)

Rust Playground

[jumpnbrownweasel]

This is the fn signature that worked for me and I think also @quinedot's first suggestion.

     fn apply(&self, func: &mut impl FnMut(&TreeItem)) {

[quinedot]

(Yes)

[John_Nagle]

Yes. That is simple and makes sense. Thanks

Compiler suggestions had led me off into the dead end of

fn apply(&self, func: impl FnMut(&TreeItem) + for<'a> std::ops::FnMut<(&'a TreeItem,)>)

[quinedot]

Yeah, those bounds mean mostly the same thing, except

• the for<'a> FnMut<(&'a TreeItem,)> version is unstable, and
• the output type of the first is () while the output type of the second could be any Sized type

so, bad diagnostics.

(for<'a> FnMut(&'a TreeItem) is stable, and means the same as FnMut(&TreeItem)).

---

Some elaboration for anyone in the audience:

First, note that a F: FnMut(..) closure^[1] is called by taking a &mut _ to the closure -- the FnMut method that corresponds to calling the closure takes &mut self. So if you take such a closure by value, for example, you have to making the binding mutable.^[2]

Next, note that without a Copy^[3] bound, passing a F: FnMut(..) closure will move it -- you'll give away ownership of the closure. So you won't be able to call it any more. But, copying^[4] such a closure would generally defeat the point of FnMut -- any state the closure was keeping track of would be cloned too, instead of maintaining that state across all the calls you make.^[5] (So adding a Copy bound isn't really what you want with FnMut either.)

The moving/ownership is the source of the original error: you can't pass it to multiple children by value.

&mut _ don't implement Copy either, but you can reborrow them. And this is the key to one of the solutions: just take a &mut F, which you can use to call the closure (FnMut::call_mut(..)), and you can reborrow the &mut F to make the recursive call.

Splitting the method up into a public method that takes a closure by value, and another that takes a &mut _, is primarily an ergonomic improvement for callers of the method, so they don't have to take a &mut to their closures themselves.

---

Finally, however, let's look at a midway approach that fails:

    // Pretty much the same as:
    // fn apply<F: FnMut(&TreeItem)>(&self, mut func: F) { .. }
    fn apply(&self, mut func: impl FnMut(&TreeItem)) {
        func(self);
        for child in &self.children {
            // Don't give away ownership, so this should work ... right?
            child.apply(&mut func)
        }
    }

The problem is that how far the recursive call goes is a dynamic property, whereas Rust needs to know every possible type parameter F that apply is called with ac compile time, because that's how generic type parameters work: every distinct type gets its own monomorphized function. So it goes something like...

• Monomorphize apply with F = F0, then...
  • Monomorphize apply with F = &mut F0, then...
    • Monomorphize apply with F = &mut &mut F0, then...
      • Monomorphize apply with F = &mut &mut &mut F0, then...

and eventually reaches a recursion limit.

Whereas with the split approach it goes something like:

• Monomorphize apply with F = F0 (parameter is F)
  • Monomorphize apply_inner with F = F0 (parameter is &mut F)
    • Calls apply_inner with F = F0 again, no need to monomorphize anything else

Using &mut dyn FnMut(..) would also avoid the infinite type recursion/monomorphization, without splitting up the method.^[6] However, it's also a bad idea! Unless you really luck out with devirtualization, you'll be adding layer of indirection every time, so at the bottom you might have a

&mut
  (&mut 
    (&mut 
      F0 
      as &mut dyn FnMut(..)
    )
    as &mut dyn FnMut(..)
  )
as &mut dyn FnMut(..)
...

as deep as your tree is.

---

1. or func: impl FnMut(..) in argument position ↩︎

2. e.g. mut func: impl FnMut(..) ↩︎

3. or perhaps Clone ↩︎

4. or cloning ↩︎

5. And if you only needed to call the closure once, presumably you would have used FnOnce. ↩︎

6. because if F: FnMut(..), then &mut F: FnMut(..), so the bound is met ↩︎