Can a while loop be rewritten using iterators?

I couldn't find any answer and I couldn't figure out myself if it is possible (I suspect it isn't, but I don't know if I am just blind or if it really is impossible).

Depends on the while loop, can you post code otherwise we can't help you

1 Like

I was wondering in general, so your answer of "it depends" already helps :wink: . Here is some code I wondered about:

pub fn factors(n: u64) -> Vec<u64> {
    let mut factors = vec![];
    let mut primes = vec![];
    let mut n = n;
    while n > 1 {
        calculate_next_prime(&mut primes);
        for &prime in primes.iter() {
            while n % prime == 0 {
                factors.push(prime);
                n /= prime;
            }
        }
    }
    factors
}

Given enough work, try_for_each can do nearly anything:

pub fn factors_iter(n: u64) -> Vec<u64> {
    let mut factors = vec![];
    let mut primes = vec![];
    let mut n = n;
    std::iter::repeat(()).try_for_each(|()|{
        if n > 1 {
            Err(())
        } else {
            calculate_next_prime(&mut primes);
            primes.iter().copied().for_each(|prime| {
                std::iter::repeat(()).try_for_each(|()|{
                    if n % prime == 0 {
                        Err(())
                    } else {
                        factors.push(prime);
                        n /= prime;
                        Ok(())
                    }
                });
            });
            Ok(())
        }
    });
    factors
}

(There's probably a better way for this scenario than that, but it demonstrates that nearly everything is possible.)

Something like https://docs.rs/itertools/0.8.0/itertools/fn.unfold.html is probably the more elegant way to do many while loops, because they are generally "shrinking" something, and you can unfold that state.

Using just std you can do this, a completely lazy iterator over all of the factors of the number you supply

fn factors(n: u64) -> impl Iterator<Item = u64> {
    let mut primes = Vec::new();
    
    let numbers = std::iter::once(2).chain(
        (1..).map(|n| (n << 1) | 1) // 2n + 1
    );

    let mut primes = numbers.filter(move |&n| {
        let is_prime = primes.iter().all(|&p| n % p != 0);
        
        if is_prime {
            primes.push(n)
        }
        
        is_prime
    });

    std::iter::successors(
        if n < 2 {
            // if n < 2, then it has no factors
            None
        } else {
            Some((
                n,      // pass in n to algorithm
                None,   // request next prime
            ))
        },
        move |&(n, prime)| {
            let prime = prime.or_else(|| primes.next())?;

            if n == 1 {
                None
            } else {
                Some(if n % prime == 0 {
                    (
                        n / prime,    // next n to use
                        Some(prime),  // we may be able to divide again with this prime
                    )
                } else {
                    (
                        n,     // could not divide, so keep last value
                        None,  // request next prime
                    )
                })
            }
        }
    )
    .flat_map(|(_, prime)| prime)
}

edit: made it even more lazy, now no loops at all (not even loop)!

2 Likes