How to compose mutable iterators?

Question

I would like to make an iterator that generates a stream of primes. My overall review process was to wrap the iterator with sequential filters, for example, you start with

let mut n = (2..N) 

Then for each prime you mutate the iterator and add it to the filter

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

I am trying to use the following code, but I cannot get it to work

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

I play with variations of this, but I can't make life and types fit. Right now the compiler is telling me

• I can not mutate self.base
• the prime variable does not live long enough

Here is the error I get

 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 

Why won't Rust let me do this?

Answer 1

Here is the working version:

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

First, I use the trait Box<Iterator> object. Boxing is inevitable, because the internal iterator must be stored somewhere between calls to next() , and with objects of reference objects there is nowhere to save it.

Secondly, I made an internal Option iterator. This is necessary because you need to replace it with a value that consumes it, so it is possible that the internal iterator may be "out" of the structure for a short time. Lack of rust patterns with Option . take() method on Option replaces the value by which it is called using None , and returns everything that was there. This is useful when shuffling non-copied objects.

Please note, however, that this implementation of the sieve will be both memory and computationally inefficient - for each step you create an additional layer of iterators that takes up a lot of space. Also, the stack depth when calling next() grows linearly with the number of primes, so you get a stack overflow on a fairly large number:

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

Launch:

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