es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Implemente un iterador de números primos similar a Haskell en Rust.

17 Jun, 2023 Programación

Estoy intentando implementar un iterador de Rust similar al siguiente código Haskell:

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

Mi intento hasta ahora (playground):

// como se señaló en un comentario, esto simplemente puede devolver Primes y no usar Box::new
fn primes() -> Box> {
Box::new(Primes::new())
}

struct Primes {
nums: Box>,
}

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 |&amp;n|!divides(prime, n));
    Some(prime)
}

}

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

Desafortunadamente, esto se encuentra con:

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></dyn><item =="" usize="">>, which does not implement the Copy trait

Para obtener más información sobre este error, intente rustc --explain E0507.

O si descomenta el código alternativo de borrow_mut:

error[E0277]: the trait bound Box<(dyn Iterator<item =="" usize=""> + 'static)>: BorrowMut<><><dyn></dyn><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<><><dyn></dyn><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:
<><t, a=””> as BorrowMut>

Francamente, ni siquiera estoy seguro de cuál de estos dos está más cerca de funcionar.</t,>

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para implementar un iterador Rust similar al código Haskell proporcionado para generar números primos, se puede usar el siguiente código:

    struct Primes {
    curr: usize,
    sieve: Vec<bool>,
}

impl Primes {
    fn new() -> Primes {
        Primes {
            curr: 2,
            sieve: vec![true; 2],
        }
    }

    fn next_prime(&mut self) -> Option<usize> {
        let curr_prime = self.curr;
        self.curr += 1;

        if self.sieve.len() <= curr_prime {
            // Expandir el criba
            let mut new_sieve = vec![true; 2 * self.sieve.len()];
            new_sieve[..self.sieve.len()].copy_from_slice(&self.sieve);
            self.sieve = new_sieve;
        }

        let mut i = curr_prime;
        while i < self.sieve.len() {
            if self.sieve[i] {
                for j in (2 * i..self.sieve.len()).step_by(i) {
                    self.sieve[j] = false;
                }
                return Some(i);
            }
            i += 1;
        }
        None
    }
}

impl Iterator for Primes {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        self.next_prime()
    }
}

    La estructura Primes mantiene el estado de la iteración en el campo curr (inicializado en 2, ya que 2 es el primer primo), y una criba de booleanos que indica si un número es primo o no. El método next_prime genera el siguiente primo iterando sobre la criba hasta que encuentra un primo, y luego marca todos los múltiplos de ese primo como compuestos en la criba. Si la criba necesita ser expandida para acomodar un nuevo primo, se redimensiona dinámicamente.

    La implementación del iterador simplemente llama a next_prime.

    Luego se puede usar este iterador de la siguiente manera:

    fn main() {
    let mut primes = Primes::new();
    for _ in 0..10 {
        println!("{}", primes.next().unwrap());
    }
}

    Esto producirá los primeros 10 primos:

    2
    3
    5
    7
    11
    13
    17
    19
    23
    29

Comments are closed.