Recursive Generator

[stustd]

I'm trying to implement a generator for the following recursive code that generates the sample locations in a multidimensional grid:

struct SampleDomain {
    pub min: f64,
    pub max: f64,
    pub n_seg: i32,  // number of segments
}
impl SampleDomain {
    pub fn values(&self) -> Vec<f64> {
        let step = (self.max - self.min) / (self.n_seg as f64);
        (0..=self.n_seg).step_by(1).map(|p| self.min + (p as f64) * step).collect()
    }
}

struct Lattice {
    pub cube: Vec<SampleDomain>,
    pub value: Vec<f64>,
}

fn main() {

    let domains = vec![
        SampleDomain { min: -2.0, max: -1.0, n_seg: 2 },
        SampleDomain { min: -1.0, max: -0.0, n_seg: 4 },
        SampleDomain { min:  0.0, max:  1.0, n_seg: 5 },
        SampleDomain { min:  1.0, max:  2.0, n_seg: 2 },
    ];

    let mut lattice = Lattice {
        cube: domains,
        value: vec![-2.0, -1.0, 0.0, 1.0],    // initial sample location
    };

    grid_points(0, &mut lattice);
    
}

fn grid_points(n: usize, lattice: &mut Lattice) {

    if n == lattice.value.len() {
        println!("{:#?}", lattice.value);
        return
    }

    for i in lattice.cube[n].values() {
        
        lattice.value[n] = i;
        grid_points(n + 1, lattice);
    }
}

How can I implement this in a generator so that I can iterate:

fn main() {
    
   // ... as before

    for gp in grid_points(0, &mut lattice) {
        println!("Gp: {:#?}",gp);
   }
}

I've been studying the genwaiter package but have problems using recursion with async. This is how far I've got:

fn main() {

    let domains = vec![
        SampleDomain { min: -2.0, max: -1.0, n_seg: 2 },
        SampleDomain { min: -1.0, max: -0.0, n_seg: 4 },
        SampleDomain { min:  0.0, max:  1.0, n_seg: 5 },
        SampleDomain { min:  1.0, max:  2.0, n_seg: 2 },
    ];
    
    let mut lattice = Lattice {
        cube: domains,
        value: vec![-2.0, -1.0, 0.0, 1.0],
    };

    let lattice = RefCell::new(lattice);
    
    for v in gen_lattice(0, lattice) {
        println!("Lattice: {:#?}", v);
    }
    
}

fn gen_lattice(n: usize, lattice: RefCell<Lattice>) -> GenBoxed<Vec<f64>> {                                                                                                                                                                     
    Gen::new_boxed(|mut co| {                                                                                                                                                                                                                   
        async move {                                                                                                                                                                                                                            
                                                                                                                                                                                                                                                
           let lat = lattice.borrow_mut();                                                                                                                                                                                                      
                                                                                                                                                                                                                                                
           if n == lat.value.len() {                                                                                                                                                                                                            
               co.yield_(lat.value.clone()).await;                                                                                                                                                                                              
            }                                                                                                                                                                                                                                   
                                                                                                                                                                                                                                                
            for i in lat.cube[n].values() {                                                                                                                                                                                                     
                lat.value[n] = i;                                                                                                                                                                                                               
                gen_lattice(n + 1, lattice);                                                                                                                                                                                                    
            }                                                                                                                                                                                                                                   
        }                                                                                                                                                                                                                                       
    })                                                                                                                                                                                                                                          
}                                                                                                                                                                                                                                                     

...producing the following err msg:

Compiling genawaiter v0.99.1 (/home/hjansen/workspace/gitspace/Simtryx/projects/following/language-specific/rust/generators/genawaiter)
error: future cannot be sent between threads safely
   --> examples/recursion_HJ_3.rs:91:5
    |
91  |     Gen::new_boxed(|mut co| {
    |     ^^^^^^^^^^^^^^ future created by async block is not `Send`
    |
    = help: the trait `std::marker::Sync` is not implemented for `std::cell::Cell<isize>`
note: future is not `Send` as this value is used across an await
   --> examples/recursion_HJ_3.rs:97:16
    |
94  |            let lat = lattice.borrow_mut();
    |                --- has type `std::cell::RefMut<'_, Lattice>` which is not `Send`
...
97  |                co.yield_(lat.value.clone()).await;
    |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ await occurs here, with `lat` maybe used later
...
104 |         }
    |         - `lat` is later dropped here
    = note: required by `genawaiter::sync::boxed::<impl genawaiter::sync::Gen<Y, R, std::pin::Pin<std::boxed::Box<(dyn std::future::Future<Output = C> + std::marker::Send + 'static)>>>>::new_boxed`

Help much appreciated!

[steffahn]

It’s not really possible to turn your "generator" into an Iterator. The problem is that your grid points all are just short-lived views of the same Vec while an Iterator returning references in Rust always needs to be returning references that all have the same lifetime. So for turning this into a proper Iterator one would need to employ some changes like e.g. cloning the whole Vec for each item and returning it by value.

Another alternative is to just not implement the Iterator interface (which also means: no for loops) but to use an alternative interface, either by manually defining a next() method and/or for_each method, or by using some existing abstraction like the streaming-iterator crate. This would include some bookkeeping though that includes getting rid of the recursion, e.g.:

#[derive(Clone)]
struct SampleDomain {
    pub min: f64,
    pub max: f64,
    pub n_seg: i32,  // number of segments
}
impl SampleDomain {
    pub fn values(&self) -> Vec<f64> {
        let step = (self.max - self.min) / (self.n_seg as f64);
        (0..=self.n_seg).step_by(1).map(|p| self.min + (p as f64) * step).collect()
    }
}

struct SampleDomainIterator {
    min: f64,
    step: f64,
    it: std::ops::RangeInclusive<i32>,
}
impl Iterator for SampleDomainIterator {
    type Item = f64;
    fn next(&mut self) -> Option<Self::Item> {
        self.it.next().map(|p| self.min + (p as f64) * self.step)
    }
}

use std::iter;
impl IntoIterator for SampleDomain {
    type Item = f64;
    type IntoIter = SampleDomainIterator;
    fn into_iter(self) -> Self::IntoIter {
        let step = (self.max - self.min) / (self.n_seg as f64);
        SampleDomainIterator {
            it: 0..=self.n_seg,
            step,
            min: self.min
        }
    }
}

struct Lattice {
    pub cube: Vec<SampleDomain>,
    pub value: Vec<f64>,
}

fn main() {

    let domains = vec![
        SampleDomain { min: -2.0, max: -1.0, n_seg: 2 },
        SampleDomain { min: -1.0, max: -0.0, n_seg: 4 },
        SampleDomain { min:  0.0, max:  1.0, n_seg: 5 },
        SampleDomain { min:  1.0, max:  2.0, n_seg: 2 },
    ];

    /*
    let mut lattice = Lattice {
        cube: domains,
        value: vec![-2.0, -1.0, 0.0, 1.0],    // initial sample location
    };

    grid_points(0, &mut lattice);
    */
    all_combinations(domains).for_each(|gp| {
        println!("Gp: {:#?}",gp);
    });

}

fn grid_points(n: usize, lattice: &mut Lattice) {

    if n == lattice.value.len() {
        println!("{:#?}", lattice.value);
        return
    }

    for i in lattice.cube[n].values() {

        lattice.value[n] = i;
        grid_points(n + 1, lattice);
    }
}


pub struct AllCombinations<T>
where
    T: IntoIterator + Clone,
{
    collections: Vec<T>,
    iterators: Vec<T::IntoIter>,
    items: Vec<T::Item>,
}

fn all_combinations<S: IntoIterator<Item = T>, T: IntoIterator + Clone>(collections: S) -> AllCombinations<T> {
    AllCombinations {
        collections: collections.into_iter().collect(),
        iterators: vec![],
        items: vec![],
    }
}

use streaming_iterator::StreamingIterator;
impl<T> StreamingIterator for AllCombinations<T>
where
    T: IntoIterator + Clone,
{
    type Item = [T::Item];
    fn get(&self) -> Option<&Self::Item> {
        match &self.items[..] {
            [] => None,
            items => Some(items),
        }
    }
    fn advance(&mut self) {
        if self.iterators.is_empty() {
            self.iterators = self.collections.iter().cloned().map(T::into_iter).collect();
            self.items = self.iterators.iter_mut().map(Iterator::next).collect::<Option<_>>().unwrap_or(vec![]);
            return;
        }
        let n = self.collections.len();
        if let Some(x) = self.iterators[n-1].next() {
            self.items[n-1] = x;
            return;
        }
        for i in (0..n-1).rev() {
            if let Some(x) = self.iterators[i].next() {
                self.items.truncate(i);
                self.items.push(x);
                self.iterators.truncate(i+1);
                self.iterators.extend(self.collections[i+1..].iter().cloned().map(T::into_iter));
                self.items.extend(self.iterators[i+1..].iter_mut().map(|it| it.next().unwrap()));
                return;
            }
        }
        self.items = vec![];
    }
}

If you don’t want to go as far and just want to keep your recursive implementation, then a for_each method is probably all you need:

struct SampleDomain {
    pub min: f64,
    pub max: f64,
    pub n_seg: i32,  // number of segments
}
impl SampleDomain {
    pub fn values(&self) -> Vec<f64> {
        let step = (self.max - self.min) / (self.n_seg as f64);
        (0..=self.n_seg).step_by(1).map(|p| self.min + (p as f64) * step).collect()
    }
}

struct Lattice {
    pub cube: Vec<SampleDomain>,
    pub value: Vec<f64>,
}

impl Lattice {
    fn for_each_grid_point<F>(&mut self, mut f: F)
    where
        F: FnMut(&[f64]),
    {
        fn visit_grid_points(n: usize, lattice: &mut Lattice, f: &mut impl FnMut(&[f64])) {

            if n == lattice.value.len() {
                f(&lattice.value);
                return
            }

            for i in lattice.cube[n].values() {

                lattice.value[n] = i;
                visit_grid_points(n + 1, lattice, f);
            }
        }
        visit_grid_points(0, self, &mut f)
    }
}

fn main() {

    let domains = vec![
        SampleDomain { min: -2.0, max: -1.0, n_seg: 2 },
        SampleDomain { min: -1.0, max: -0.0, n_seg: 4 },
        SampleDomain { min:  0.0, max:  1.0, n_seg: 5 },
        SampleDomain { min:  1.0, max:  2.0, n_seg: 2 },
    ];

    let mut lattice = Lattice {
        cube: domains,
        value: vec![-2.0, -1.0, 0.0, 1.0],    // initial sample location
    };

    //grid_points(0, &mut lattice);
    lattice.for_each_grid_point(|gp| {
        println!("Gp: {:#?}",gp);
    });

}

fn grid_points(n: usize, lattice: &mut Lattice) {

    if n == lattice.value.len() {
        println!("{:#?}", lattice.value);
        return
    }

    for i in lattice.cube[n].values() {

        lattice.value[n] = i;
        grid_points(n + 1, lattice);
    }
}

[stustd]

@steffahn Thanks a lot (glad to hear it wasn't trivial...:-). The streaming-iterator solution is verbose and breaks away from the efficient underlying recursion simplicity. The for_each solution is principally functional and may be a better candidate here... I 'm struggling though to accept that there isn't a clean(er) solution, but Rust's borrow-checker architecture may be unyieldingly regimental here.

[2e71828]

@stustd

I 'm struggling though to accept that there isn't a clean(er) solution, but Rust's borrow-checker architecture may be unyieldingly regimental here.

I think you should be able to make the iterator return something like this, but I'm having trouble figuring out exactly what that would look like:

struct LatticeEntry<'a> {
    lattice: Rc<RefCell<&'a mut Vec<f64>>>,
    idx: usize
}

impl<'a> LatticeEntry<'a> {
    pub fn update<O>(&mut self, f:impl FnOnce(&mut f64)->O {
        let lattice = self.lattice.borrow_mut();
        f(&mut lattice[self.idx])
    }
}

(untested)

[kornel]

That RefCell isn't doing anything here. &mut is always exclusive, no matter where you put it, so you can't "undo" its strict exclusivity rules by wrapping it in another type.

If you want shared mutable access, you'll need RefCell<Vec<f64>>.

[2e71828]

That's what the Rc is for: there's only one RefCell<&mut _> throughout the course of the iteration, so there's no possible aliasing, though the original reference can't be used again until the iterator and all its products are destroyed.

I got the general strategy working in the playground but don't understand @stustd's code well enough to adapt it:

#[derive(Debug)]
struct MyVec<T>(Vec<T>);

struct IterMut<'a, T> {
    vec: Rc<RefCell<&'a mut MyVec<T>>>,
    next_pos: usize,
    len: usize
}

struct Entry<'a, T> {
    vec: Rc<RefCell<&'a mut MyVec<T>>>,
    pos: usize
}

impl<T> MyVec<T> {
    fn iter_mut(&mut self)->IterMut<'_,T> {
        let len = self.0.len();
        IterMut {
            vec: Rc::new(RefCell::new(self)),
            next_pos: 0,
            len
        }
    }
}


impl<'a,T> Iterator for IterMut<'a,T> {
    type Item = Entry<'a,T>;
    fn next(&mut self)->Option<Entry<'a,T>> {
        if self.next_pos < self.len {
            self.next_pos += 1;
            Some(Entry {
                vec: Rc::clone(&self.vec),
                pos: self.next_pos - 1
            })
        } else {
            None
        }
    }
}

[stustd]

@2e71828 Thanks for the example. I prefer not to break away from the underlying simple recursive scheme and opt to first fully generate all samples (i.e. avoiding a generator) and implement a next() wrapper around it. Time will tell whether recursion and generators can be combined someway or another...