Методы превращения рекурсивных функций в итераторы в Rust? - PullRequest
Новая
       37

Методы превращения рекурсивных функций в итераторы в Rust?

0 голосов
/ 10 июля 2020

Я изо всех сил пытаюсь превратить простую рекурсивную функцию в простой итератор. Проблема в том, что рекурсивная функция поддерживает состояние в своих локальных переменных и стеке вызовов - и чтобы превратить это в итератор ржавчины, означает в основном экстернализацию всего состояния функции в изменяемые свойства в некоторой настраиваемой структуре итератора. Это довольно неприятное занятие.

В таких языках, как javascript или python, yield приходит на помощь. Есть ли в Rust какие-нибудь методы, которые помогут справиться с этой сложностью?

Простой пример с использованием yield (псевдокод): 

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, я в основном создаю a Vec<Vec<State>> в моей структуре итератора, чтобы отразить данные, возвращаемые next_states_from на каждом уровне стека вызовов. Затем при каждом вызове next() аккуратно вытаскивайте из него кусочки, чтобы восстановить состояние. Кажется, я чего-то упускаю.

1 Ответ

1 голос
/ 10 июля 2020

Вы выполняете (с ограничением по глубине) поиск в глубину на вашем графике состояний. Вы можете делать это итеративно, используя один стек необработанных поддеревьев (в зависимости от структуры вашего графа состояний). 

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));
    }
}

Есть некоторые небольшие отличия от вашего кода:

  • Итератор возвращает значение элемента root, а ваша версия - нет. Это можно легко исправить, используя .skip(1)
  • Дочерние элементы обрабатываются в порядке справа налево (в обратном порядке по сравнению с результатом next_states_from). В противном случае вам нужно будет изменить порядок нажатия следующих состояний (в зависимости от типа результата next_states_from вы можете просто использовать .rev(), в противном случае вам понадобится временный)
...