Implementing Iterator using an underlying iterator

Question

Editor's note: This question uses some functions and types that were removed before Rust 1.0. The ideas are still valid but the code does not run in Rust 1.0.

I'm trying to solve Project Euler's problem #3 using Rust by implementing Eratosthenes Sieve as an iterator.

After some brain-exploding tries with lifetimes, I stopped here.

use std::iter::count;

struct EratosthenesStream<'a> {
    sieve: &'a (Iterator + 'a),
}

impl<'a> EratosthenesStream<'a> {
    fn new() -> EratosthenesStream<'a> {
        EratosthenesStream {
            sieve: &count(2, 1),
        }
    }
}

impl<'a> Iterator for EratosthenesStream<'a> {
    type Item = isize;

    fn next(&mut self) -> Option<isize> {
        let prime = self.sieve.next().expect("Out of numbers");
        self.sieve = self.sieve.filter(|&x| x % prime == 0);
        Some(prime)
    }
}

fn main() {
    // let sieve = EratosthenesStream::new();
    // for i in sieve.take(5) {
    //   println!("{}", i);
    // }
}

Building that thing gives me:

Compiling problem3 v0.0.1 (file:///home/franza/Projects/euler-project-rust/problem3)
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:16:33: 16:45 error: the value of the associated type `Item` (from the trait `core::iter::Iterator`) must be specified
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:16     EratosthenesStream { sieve: &count(2, 1) }
                                                                                                 ^~~~~~~~~~~~
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25:29: 25:56 error: type `&'a core::iter::Iterator + 'a` does not implement any method in scope named `filter`
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25     self.sieve = self.sieve.filter(|&x| x % prime == 0);
                                                                                             ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25:41: 25:42 error: the type of this value must be known in this context
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25     self.sieve = self.sieve.filter(|&x| x % prime == 0);
                                                                                                         ^
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25:36: 25:55 error: can't infer the "kind" of the closure, explicitly annotate it. e.g. `|&:| {}`
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25     self.sieve = self.sieve.filter(|&x| x % prime == 0);
                                                                                                    ^~~~~~~~~~~~~~~~~~~
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:26:5: 26:16 error: mismatched types: expected `core::option::Option<isize>`, found `core::option::Option<<core::iter::Iterator as core::iter::Iterator>::Item>` (expected isize, found associated type)
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:26     Some(prime)
                                                                     ^~~~~~~~~~~
error: aborting due to 5 previous errors
Could not compile `problem3`.

I'm starting out in Rust so I don't know a lot about this

UPDATE:

• rustc 1.0.0-nightly (44a287e6e 2015-01-08 17:03:40 -0800)
• cargo 0.0.1-pre-nightly (8c01b6b 2015-01-08 20:52:43 +0000)

Answer 1

Editor's note: This answer uses some functions and types that were removed before Rust 1.0. The ideas are still valid but the code does not run in Rust 1.0. Some bugs have been fixed since then as well.

This is an interesting approach to computing primes, but I'm not sure it's going to work well with Rust as it stands right now. There's a lot of bugs we're ironing out with trait objects that make them... not great.

Still, I can address some issues.

You're trying to store a shared reference to the iterator in your struct. That's not going to work for two reasons: iterators require mutability for next, and the iterators aren't going to live long enough.

Presumably, you want something like Box<Iterator + 'static> in your struct, but due to the aforementioned bugs, that just doesn't work for no particularly good reason.

For now I'm afraid you'll have to maintain the list of primes you've seen explicitly. I suggest something like:

struct Foo {
    odds: Counter<u32>,
    primes: Vec<u32>,
}

And a more "procedural" approach with explicit for-loops:

(not sure if it's totally appropriate to give a full solution here, so don't read ahead if you don't want spoilers, I guess?)

struct Foo {
    odds: Counter<u32>,
    primes: Vec<u32>,
}

impl Foo {
    fn new() -> Foo {
        Foo {
            odds: count(2, 1),
            primes: Vec::new(),
        }
    }
}

impl Iterator for Foo {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        'main: for i in self.odds {
            for &prime in self.primes.iter() {
                if i % prime == 0 {
                    continue 'main;
                }
            }
            self.primes.push(i);
            return Some(i);
        }
        None
    }
}

fn main() {
    let foo = Foo::new();
    for i in foo.take(10) {
        println!("{}", i);
    }
}

Answer 2

Now that #21361 has been closed, you can implement it this way:

use std::{iter, mem};

struct Sieve {
    iter: Box<Iterator<Item = u64> + 'static>,
}

impl Sieve {
    fn new() -> Sieve {
        Sieve {
            iter: Box::new(2..),
        }
    }
}

impl Iterator for Sieve {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let mut iter = mem::replace(&mut self.iter, Box::new(iter::empty()));

        match iter.next() {
            Some(prime) => {
                self.iter = Box::new(iter.filter(move |x| x % prime != 0));
                Some(prime)
            }
            None => None,
        }
    }
}

fn main() {
    let v: Vec<_> = Sieve::new().take(20).collect();
    println!("{:?}", v);
}

Some notes about the implementation:

1. Your logic was backwards. You want to filter x % prime != 0. ^_^
2. filter consumes the iterator, but that would cause problem here. If we were allowed to consume it, then the Sieve struct would no longer be whole and valid. To work around this, we use mem::replace to put in a placeholder value. That lets us consume the iterator before we update the struct with the new value.
3. Every iteration adds more function calls to the stack. I was only able get the first 6466 prime numbers with this technique before I ran out of stack space.

Answer 3

The key of this problem is to filter the iterator without moving it, which can be done by using take_mut.

Add take_mut = "0.2.2"(or any other compatible versions) to your dependencies, then you can do something like:

extern crate take_mut;

struct Primes {
    iter: Box<Iterator<Item=i64>>,
}

impl Iterator for Primes {
    type Item=i64;

    fn next(&mut self) -> Option<i64> {
        let result = self.iter.next();
        if let Some(prime) = result {
            take_mut::take(&mut self.iter, 
                |primes| Box::new(primes.filter(move |p| p % prime != 0)));
        }
        result
    }
}

impl Primes {
    fn new() -> Primes {
        Primes { iter: Box::new(2..)}
    }
}

fn main() {
    println!("First 10 primes:");
    for p in Primes::new().take(10) {
        println!("{}", p);
    }
}

Edit: Option::take can also do this job.

struct Primes {
    iter: Option<Box<Iterator<Item = u64>>>,
}

impl Primes {
    fn new() -> Primes {
        Primes {
            iter: Some(Box::new(2..)),
        }
    }
}

impl Iterator for Primes {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let mut iter = self.iter.take()?;
        let result = iter.next();
        if let Some(prime) = result {
            self.iter = Some(Box::new(iter.filter(move |n| n % prime != 0)));
        }
        result
    }
}