How to pass a closure as parameter recursively?

Question

The problem

I am building the pre-order traversal for an n-tree, in such a way a closure is given to be executed for each node in the traversal.

My first approach was the following:

#[derive(Debug)]
pub struct Node<T> {
    value: T,
    children: Vec<Node<T>>,
}

impl<T> Node<T> {
    pub fn preorder<F>(&self, mut f: F)
    where
        F: FnMut(&Self),
    {
        f(self);
        self.children.iter().for_each(|child| child.preorder(f));
    }
}

However I am facing an error when calling the child.preorder(f) statement inside the foreach iterator.

error[E0507]: cannot move out of `f`, a captured variable in an `FnMut` closure
  --> src/lib.rs:12:62
   |
7  |     pub fn preorder<F>(&self, mut f: F)
   |                               ----- captured outer variable
...
12 |         self.children.iter().for_each(|child| child.preorder(f));
   |                                       -------                ^ move occurs because `f` has type `F`, which does not implement the `Copy` trait
   |                                       |
   |                                       captured by this `FnMut` closure

Playground

Solutions I found

Changing the header of the pre-order method to the following compiles perfectly, but it sets a Copy requisite on the closure to be used that I do not want at all.

pub fn preorder<F>(&self, mut f: F)
    where
        F: FnMut(&Self) + Copy,

Another way I found to workaround the Copy requisite on the closure is by using an immersion method like the following (see it in the playground):

pub struct Node<T> {
    value: T,
    children: Vec<Node<T>>,
}

impl<T> Node<T> {
    fn preorder_immersion<F>(&self, f: &mut F)
    where
        F: FnMut(&Self),
    {
        f(self);
        self.children
            .iter()
            .for_each(|child| child.preorder_immersion(f));
    }

    pub fn preorder_mut<F>(&self, mut f: F)
    where
        F: FnMut(&Self),
    {
        self.preorder_immersion(&mut f);
    }
}

Sincerely, that is painful to watch. Basically because it implies to have two methods for each traversal implementation.

What I want

It would be great to be able to do something like this when invoking the pre-order method:

let mut result = Vec::new();
node.preorder(|n| result.push(*n.value()));

And the latest solution I gave works fine.

My question: is there any more elegant way to do so? Am I missing something? Or is OK to use the immersion approach?

Answer 1

Like I said in a comment earlier I'd go with an Iterator based approach, while exploring I found this solution which is quite elegant in my opinion:

impl<T> Node<T> {
    pub fn preorder(&self) -> impl Iterator<Item = &Self> {
        Iter::new(self)
    }
}

struct Iter<'a, T> {
    left: Vec<&'a Node<T>>,
}

impl<'a, T> Iter<'a, T> {
    fn new(root: &'a Node<T>) -> Self {
        Self { left: vec![root] }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a Node<T>;
    fn next(&mut self) -> Option<Self::Item> {
        let current = self.left.pop()?;
        self.left.extend(current.children.iter().rev());
        Some(current)
    }
}

We store nodes we have yet to yield in a Vec, in reverse so that we can use pop and extend which should be quite efficient. Whenever we yield a Node we add it's children to the remaining Nodes.

Instead of using it like this node.preorder(your_closure_or_function) you'd use it like node.preorder().for_each(your_closure_or_function), but for the small price of an extra function call you get the whole power and toolset already built around iterators in Rust.