在Rust中将递归函数转换为迭代器的技术? [英] Techniques for turning recursive functions into iterators in Rust?

问题描述

我正在努力将简单的递归函数转换为简单的迭代器.问题在于递归函数在其局部变量中保持状态并调用堆栈-并将其转换为rust迭代器意味着基本上将所有函数状态外部化为某个自定义迭代器结构上的可变属性.相当麻烦.

I'm struggling to turn a simple recursive function into a simple iterator. The problem is that the recursive function maintains state in its local variables and call stack -- and to turn this into a rust iterator means basically externalizing all the function state into mutable properties on some custom iterator struct. It's quite a messy endeavor.

使用诸如javascript或python之类的语言，可以抢救yield. Rust中是否有任何技术可以帮助管理这种复杂性?

In a language like javascript or python, yield comes to the rescue. Are there any techniques in Rust to help manage this complexity?

使用yield(伪代码)的简单示例:

Simple example using yield (pseudocode):

function one_level(state, depth, max_depth) {
  if depth == max_depth {
    return
  }
  for s in next_states_from(state) {
    yield state_to_value(s);
    yield one_level(s, depth+1, max_depth);
  }
}

要在Rust中进行类似的工作，我基本上是在迭代器结构上创建一个Vec<Vec<State>>，以反映在调用堆栈的每个级别上next_states_from返回的数据.然后，对于每个next()调用，请仔细弹出此部分以恢复状态.我觉得我可能会丢失一些东西.

To make something similar work in Rust, I'm basically creating a Vec<Vec<State>> on my iterator struct, to reflect the data returned by next_states_from at each level of the call stack. Then for each next() invocation, carefully popping pieces off of this to restore state. I feel like I may be missing something.

推荐答案

您正在执行(深度受限)

You are performing a (depth-limited) depth-first search on your state graph. You can do it iteratively by using a single stack of unprocessed subtrees(depending on your state graph structure).

struct Iter {
    stack: Vec<(State, u32)>,
    max_depth: u32,
}

impl Iter {
    fn new(root: State, max_depth: u32) -> Self {
        Self {
            stack: vec![(root, 0)],
            max_depth
        }
    }
}

impl Iterator for Iter {
    type Item = u32; // return type of state_to_value
    fn next(&mut self) -> Option<Self::Item> {
        let (state, depth) = self.stack.pop()?;
        if depth < self.max_depth {
            for s in next_states_from(state) {
                self.stack.push((s, depth+1));
            }
        }
        return Some(state_to_value(state));
    }
}

您的代码略有不同:

• 迭代器产生根元素的值，而您的版本则不.使用.skip(1)
可以轻松解决此问题
• 按从右到左的顺序处理孩子(与next_states_from的结果相反).否则，您将需要颠倒下一个状态的顺序(取决于next_states_from的结果类型，您可以只使用.rev()，否则您将需要一个临时的)

• The iterator yields the value of the root element, while your version does not. This can be easily fixed using .skip(1)
• Children are processed in right-to-left order (reversed from the result of next_states_from). Otherwise, you will need to reverse the order of pushing the next states (depending on the result type of next_states_from you can just use .rev(), otherwise you will need a temporary)

这篇关于在Rust中将递归函数转换为迭代器的技术?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！