Как создать изменяемые итераторы?

Question

Я хотел бы сделать итератор, который генерирует поток простых чисел. Мой общий мыслительный процесс был обернуть итератор с последовательными фильтрами так, например, начать с

let mut n = (2..N) 

Тогда для каждого простого числа вы мутировать итератор и добавить на фильтре

let p1 = n.next() 
n = n.filter(|&x| x%p1 !=0) 
let p2 = n.next() 
n = n.filter(|&x| x%p2 !=0) 

Я пытаюсь используйте следующий код, но я не могу заставить его работать

struct Primes { 
    base: Iterator<Item = u64>, 
} 

impl<'a> Iterator for Primes<'a> { 
    type Item = u64; 

    fn next(&mut self) -> Option<u64> { 
     let p = self.base.next(); 
     match p { 
      Some(n) => { 
       let prime = n.clone(); 
       let step = self.base.filter(move |&: &x| {x%prime!=0}); 
       self.base = &step as &Iterator<Item = u64>; 
       Some(n)     
      }, 
      _ => None 
     }   
    } 
} 

Я поиграл с вариациями, но я не могу показаться, чтобы получить время жизни и типы совпасть. Сейчас компилятор говорит мне

1. Я не могу мутировать self.base
2. переменная премьер не живут достаточно долго

Здесь ошибка я получаю

solution.rs:16:17: 16:26 error: cannot borrow immutable borrowed content `*self.base` as mutable 
solution.rs:16   let p = self.base.next(); 
                ^~~~~~~~~ 
solution.rs:20:28: 20:37 error: cannot borrow immutable borrowed content `*self.base` as mutable 
solution.rs:20     let step = self.base.filter(move |&: &x| {x%prime!=0}); 
                   ^~~~~~~~~ 
solution.rs:21:30: 21:34 error: `step` does not live long enough 
solution.rs:21     self.base = &step as &Iterator<Item = u64>; 
                    ^~~~ 
solution.rs:15:39: 26:6 note: reference must be valid for the lifetime 'a as defined on the block at 15:38... 
solution.rs:15  fn next(&mut self) -> Option<u64> { 
solution.rs:16   let p = self.base.next(); 
solution.rs:17   match p { 
solution.rs:18    Some(n) => { 
solution.rs:19     let prime = n.clone(); 
solution.rs:20     let step = self.base.filter(move |&: &x| {x%prime!=0}); 
            ... 
solution.rs:20:71: 23:14 note: ...but borrowed value is only valid for the block suffix following statement 1 at 20:70 
solution.rs:20     let step = self.base.filter(move |&: &x| {x%prime!=0}); 
solution.rs:21     self.base = &step as &Iterator<Item = u64>; 
solution.rs:22     Some(n)     
solution.rs:23    }, 
error: aborting due to 3 previous errors 

Почему Rust не позволил мне сделать это?

Answer 1

Вот рабочая версия:

struct Primes<'a> { 
    base: Option<Box<Iterator<Item=u64>+'a>>, 
} 

impl<'a> Iterator for Primes<'a> { 
    type Item = u64; 

    fn next(&mut self) -> Option<u64> { 
     let p = self.base.as_mut().unwrap().next(); 
     p.map(|n| { 
      let base = self.base.take(); 
      let step = base.unwrap().filter(move |x| x % n != 0); 
      self.base = Some(Box::new(step)); 
      n     
     }) 
    } 
} 

impl<'a> Primes<'a> { 
    #[inline] 
    pub fn new<I: Iterator<Item=u64>+'a>(r: I) -> Primes<'a> { 
     Primes { 
      base: Some(Box::new(r)) 
     } 
    } 
} 

fn main() { 
    for p in Primes::new(2..).take(32) { 
     print!("{} ", p); 
    } 
    println!(""); 
} 

Во-первых, я использую Box<Iterator> объекта признака. Бокс неизбежен, потому что внутренний итератор должен храниться где-то между вызовами, а с объектами ссылочных объектов его нигде нельзя сохранить.

Во-вторых, я сделал внутренний итератор Option. Это необходимо, потому что вам нужно заменить его на значение, которое его потребляет, поэтому возможно, что внутренний итератор может «отсутствовать» из структуры на короткое время. Отсутствие моделей ржавчины с Option. take() метод на Option заменяет значение, на которое он вызывается, с None и возвращает все, что там было. Это полезно при перемещении объектов, не подлежащих копированию.

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

fn main() { 
    println!("{}", Primes::new(2..).nth(10000).unwrap()); 
} 

Забегая:

% ./test1 

thread '<main>' has overflowed its stack 
zsh: illegal hardware instruction (core dumped) ./test1