How to compose mutable Iterators?

Question

Editor's note: This code example is from a version of Rust prior to 1.0 and is not syntactically valid Rust 1.0 code. Updated versions of this code produce different errors, but the answers still contain valuable information.

I would like to make an iterator that generates a stream of prime numbers. My general thought process was to wrap an iterator with successive filters so for example you start with

let mut n = (2..N)

Then for each prime number you mutate the iterator and add on a 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 can not seem to 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 have toyed with variations of this, but I can't seem to get lifetimes and types to match up. Right now the compiler is telling me

I can't mutate self.base
the variable prime doesn't live long enough

Here is the error I am getting

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?

Shepmaster · Accepted Answer · 2018-07-06 18:10:42Z

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

I'm using a Box<Iterator> trait object. Boxing is unavoidable because the internal iterator must be stored somewhere between next() calls, and there is nowhere you can store reference trait objects.

I made the internal iterator an Option. This is necessary because you need to replace it with a value which consumes it, so it is possible that the internal iterator may be "absent" from the structure for a short time. Rust models absence with Option. Option::take replaces the value it is called on with None and returns whatever was there. This is useful when shuffling non-copyable objects around.

Note, however, that this sieve implementation is going to be both memory and computationally inefficient - for each prime you're creating an additional layer of iterators which takes heap space. Also the depth of stack when calling next() grows linearly with the number of primes, so you will get a stack overflow on a sufficiently large number:

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

Running it:

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

and with reference trait objects there is nowhere you can store it - additionally, the actual size of the iterator base changes as it gets more and more nested. Thus, we need to use heap-allocation so that the size of Primes is always constant.
@Shepmaster, The size of reference trait object does not change, afaik. The only reason it can't be used is ownership.
The size is indeed constant. Every layer is a box around Filter<Box<Iterator>, Closure>, the size of the closure is constant (captures one u64).
@VladimirMatveev ah, good point. I thought it was a generic type, not a trait object.

Collectives™ on Stack Overflow

How to compose mutable Iterators?

1 Answer 1

4 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Related