haskell - 在 Rust 中实现类似 Haskell 的素数迭代器

Question

我正在尝试实现一个类似于以下 Haskell 代码的 Rust 迭代器:

primes :: [Integer]
primes = nextPrime [2..]
    where 
        nextPrime (x:xs) = x : nextPrime (filter (notDivBy x) xs)
        notDivBy a x = a `mod` x /= 0

到目前为止我的尝试(playground):

// as pointed out in a comment this can simply return Primes and not use Box::new
fn primes() -> Box<dyn Iterator<Item = usize>> {
    Box::new(Primes::new())
}

struct Primes {
    nums: Box<dyn Iterator<Item = usize>>,
}

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

impl Iterator for Primes {
    type Item = usize;
    
    fn next(&mut self) -> Option<usize> {
        
        let prime = self.nums.next().unwrap();
        self.nums = Box::new(self.nums.filter(move |&n|!divides(prime, n)));
        //use std::borrow::BorrowMut;
        //*self.nums.borrow_mut() = self.nums.filter(move |&n|!divides(prime, n));
        Some(prime)
    }
}


pub fn divides(d: usize, n: usize) -> bool {
    n % d == 0
}

不幸的是，这会遇到:

error[E0507]: cannot move out of `self.nums` which is behind a mutable reference
  --> src/lib.rs:22:30
   |
22 |         self.nums = Box::new(self.nums.filter(move |&n| !divides(prime, n)));
   |                              ^^^^^^^^^ move occurs because `self.nums` has type `Box<dyn Iterator<Item = usize>>`, which does not implement the `Copy` trait

For more information about this error, try `rustc --explain E0507`.

或者，如果您取消注释替代的borrow_mut代码:

error[E0277]: the trait bound `Box<(dyn Iterator<Item = usize> + 'static)>: BorrowMut<Filter<Box<dyn Iterator<Item = usize>>, [closure@src/lib.rs:24:52: 24:79]>>` is not satisfied
  --> src/lib.rs:24:20
   |
24 |         *self.nums.borrow_mut() = self.nums.filter(move |&n|!divides(prime, n));
   |                    ^^^^^^^^^^ the trait `BorrowMut<Filter<Box<dyn Iterator<Item = usize>>, [closure@src/lib.rs:24:52: 24:79]>>` is not implemented for `Box<(dyn Iterator<Item = usize> + 'static)>`
   |
   = help: the following implementations were found:
             <Box<T, A> as BorrowMut<T>>

坦白说，我什至不确定这两者中哪一个更接近工作。

Answer 1

我认为你可以缓存发现的素数:

fn primes() -> Primes {
    Primes::new()
}

struct Primes {
    nums: Box<dyn Iterator<Item = usize>>,
    cache: Vec<usize>,
}

impl Primes {
    fn new() -> Self {
        Primes {
            nums: Box::new(2..),
            cache: Vec::new(),
        }
    }
}

impl Iterator for Primes {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        loop {
            let num = self.nums.next().unwrap();
            if self
                .cache
                .iter()
                .take_while(|&&n| n*n <= num)
                .all(|&p| !divides(p, num))
            {
                // we found a prime!
                self.cache.push(num);
                return Some(num);
            }
        }
    }
}

pub fn divides(d: usize, n: usize) -> bool {
    n % d == 0
}

fn main() {
    println!("Primes: {:?}", primes().take(10).collect::<Vec<_>>());
}

Playground