Làm cách nào để soạn Iterator có thể thay đổi?

Question

Tôi muốn tạo một trình lặp tạo ra một luồng các số nguyên tố. quá trình suy nghĩ chung của tôi là quấn một iterator với các bộ lọc liên tiếp ví dụ như vậy bạn bắt đầu với

let mut n = (2..N) 

Sau đó, đối với mỗi số nguyên tố bạn biến những iterator và thêm vào một bộ lọc

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

Tôi cố gắng để sử dụng đoạn mã sau, nhưng tôi dường như không thể làm cho nó hoạt

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

tôi đã đùa giỡn với các biến thể của việc này, nhưng tôi dường như không thể có được tuổi thọ và các loại để phù hợp lên. Ngay bây giờ các trình biên dịch là nói cho tôi

1. Tôi không thể đột biến self.base
2. thủ biến không sống đủ lâu

Đây là lỗi Tôi nhận

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 

Tại sao Rust không cho phép tôi thực hiện việc này?

Answer 1

Đây là một phiên bản làm việc:

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!(""); 
} 

Trước tiên, tôi đang sử dụng Box<Iterator> đối tượng tính trạng. Boxing là không thể tránh khỏi vì iterator nội bộ phải được lưu trữ ở đâu đó giữa các cuộc gọi next() và với các đối tượng tra cứu không có nơi nào bạn có thể lưu trữ nó.

Thứ hai, tôi đã tạo bộ lặp nội bộ là Option. Điều này là cần thiết bởi vì bạn cần thay thế nó bằng một giá trị tiêu thụ nó, vì vậy có khả năng trình lặp nội bộ có thể "vắng mặt" từ cấu trúc trong một thời gian ngắn. Các mô hình Rust vắng mặt với Option. Phương pháp take() trên Option thay thế giá trị được gọi là None và trả lại mọi thứ ở đó. Điều này rất hữu ích khi xáo trộn các đối tượng không thể sao chép xung quanh. Tuy nhiên, lưu ý rằng việc thực hiện sàng này sẽ là cả bộ nhớ và tính toán kém hiệu quả - đối với mỗi nguyên tố, bạn đang tạo ra một lớp bổ sung các trình vòng lặp chiếm không gian heap. Ngoài ra độ sâu của ngăn xếp khi gọi next() tăng tuyến tính với số lượng số nguyên tố, vì vậy bạn sẽ nhận được một chồng tràn vào một số đủ lớn:

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

Chạy nó:

% ./test1 

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