Jak komponować zmienne Iteratory?

Question

Chciałbym zrobić iterator, który generuje strumień liczb pierwszych. Mój ogólny proces myślowy było owinąć iterator z kolejnych filtrów tak na przykład zacząć

let mut n = (2..N) 

Następnie dla każdej liczby pierwszej ty zmutować iterator i dodać na filtrze

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

próbuję należy użyć następującego kodu, ale nie wydaje się uzyskać go do pracy

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

mam bawił się z odmian tego, ale nie wydaje się uzyskać wcieleń i typów, aby dopasować się. Teraz kompilator mówi mi

1. Nie mogę mutować self.base
2. zmienna prime nie żyje wystarczająco długo

Tutaj jest błąd otrzymuję

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 

Dlaczego Rust nie pozwala mi tego zrobić?

Answer 1

Oto wersja robocza:

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

Najpierw używam Box<Iterator> cecha obiektu. Boks jest nieunikniony, ponieważ wewnętrzny iterator musi być przechowywany gdzieś pomiędzy rozmowami next(), a przy obiektach referencyjnych nie ma miejsca, gdzie można go zapisać.

Po drugie, wykonałem wewnętrzny iterator Option. Jest to konieczne, ponieważ trzeba go zastąpić wartością, która je zużywa, więc możliwe jest, że wewnętrzny iterator może być "nieobecny" w strukturze przez krótki czas. Nieobecność modeli rdzy z Option. take() metoda na Option zastępuje wartość, z którą jest wywoływana, z None i zwraca to, co tam było. Jest to przydatne podczas tasowania obiektów, które nie mogą być kopiowane.

Należy jednak pamiętać, że ta implementacja sita ma być zarówno pamięcią, jak i nieefektywną obliczeniowo - dla każdego primera tworzona jest dodatkowa warstwa iteratorów, która zajmuje przestrzeń sterty. Również głębokość stosu podczas wywoływania next() rośnie liniowo wraz ze wzrostem liczby liczb pierwszych, więc dostaniesz przepełnienie stosu na wystarczająco dużej liczby:

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

Running go:

% ./test1 

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