How to recursively improve an iterator without needing to use a vec

From zulip thread. Although, as @lcnr pointed out that this is not necessarily a bottleneck for my algorithm, I would like to learn how to do this with just iterators and not vec.

The issue is that the borrow-checker wants me to make the inner closure move, but then I cannot keep track of the group count to correctly number my combinations.

pub fn get_combinations(all_values: &ValueSet) -> BTreeMap<Value, Vec<Combination>> {
    let simple_values = &all_values.simple;
    let comb_max = (2_usize.pow((simple_values.len()) as u32));
    let mut values = Box::new((1..comb_max).map(|v| {
        let value = get_combination_value(&v, all_values);
        Combination { value, combination: v }
    })) as Box<dyn Iterator<Item = Combination>>;

    if let Some(grouped_values) = &all_values.complex {
        let mut prevcount = simple_values.len();
        for cur_group in grouped_values {
            let count = prevcount;
            prevcount += grouped_values.len();
            values = Box::new(values.flat_map(move |prev_c| {
                cur_group.iter().enumerate().map(|(i, v)| {
                    Combination {
                        value: prev_c.value + v,
                        combination: prev_c.combination + (1 << (count + i)),
                    }
                })
            }));
        };
    }

    values.fold(BTreeMap::new(), |mut acc, c| {
        acc.entry(c.value).or_insert(Vec::new()).push(c);
        acc
    })
}

And the error is:

error: captured variable cannot escape `FnMut` closure body
  --> src/Comparer.rs:90:17
   |
87 |               let count = prevcount;
   |                   ----- variable defined here
88 |               prevcount += grouped_values.len();
89 |               values = Box::new(values.flat_map(move |prev_c:Combination| {
   |                                                                         - inferred to be a `FnMut` closure
90 | /                 cur_group.iter().enumerate().map(|(i, v)| {
91 | |                     Combination {
92 | |                         value: prev_c.value + v,
93 | |                         combination: prev_c.combination + (1 << (count + i)),
   | |                                                                  ----- variable captured here
94 | |                     }
95 | |                 })
   | |__________________^ returns a reference to a captured variable which escapes the closure body
   |
   = note: `FnMut` closures only have access to their captured variables while they are executing...
   = note: ...therefore, they cannot allow references to captured variables to escape

Is there a different way for me to make values consume the previous version of itself and create a new iterator of the result.

Before trying this out, I simply made values into a Vec, and created a new Vec for each iteration of the grouped_values (pre-allocating the vec, since the capacity is predictable), and made values = new_values. This is the working version using Vec's - I think that it is good enough, but I want to know if it is possible to do the same without creating intermediary storage - b/c in theory, this algorithm only needs to iterate over all the values once.

pub fn get_combinations(all_values: &ValueSet) -> BTreeMap<Value, Vec<Combination>> {
    let simple_values = &all_values.simple;
    let comb_max = (2_usize.pow((simple_values.len()) as u32));
    let mut values = (1..comb_max).map(|v| {
        let value = get_combination_value(&v, all_values);
        Combination { value, combination: v }
    }).collect::<Vec<Combination>>();

    if let Some(grouped_values) = &all_values.complex {
        let mut count = simple_values.len();
        for cur_group in grouped_values {
            let mut new_values = Vec::with_capacity(count * cur_group.len());
            for prev_c in &values {
                for (i, v) in cur_group.iter().enumerate() {
                    new_values.push(Combination {
                        value: prev_c.value + v,
                        combination: prev_c.combination + (1 << (count + i)),
                    });
                }
                new_values.push(*prev_c);
            }
            count += cur_group.len();
            values = new_values;
        };
    }

    values.iter().fold(BTreeMap::new(), |mut acc, c| {
        acc.entry(c.value).or_insert(Vec::new()).push(*c);
        acc
    })
}

Will putting a move on that |(i, v)| closure help? It would be easier to solve this if the example was more complete so that we yould reproduce the compilation error ourselves and see definitions of the types involved.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=25ab297354de096eeb2e598e1e620840

Thanks for the link—but also... it already compiles with that move!! :wink:


pub fn get_combinations(all_values: &ValueSet) -> BTreeMap<Value, Vec<Combination>> {
    let simple_values = &all_values.simple;
    let comb_max = (2_usize.pow((simple_values.len()) as u32));
    let mut values = Box::new((1..comb_max).map(|v| {
        let value = get_combination_value(&v, all_values);
        Combination { value, combination: v }
    })) as Box<dyn Iterator<Item = Combination>>;

    if let Some(grouped_values) = &all_values.complex {
        let mut prevcount = simple_values.len();
        for cur_group in grouped_values {
            let count = prevcount;
            prevcount += grouped_values.len();
            values = Box::new(values.flat_map(move |prev_c| {
-               cur_group.iter().enumerate().map(|(i, v)| {
+               cur_group.iter().enumerate().map(move |(i, v)| {
                    Combination {
                        value: prev_c.value + v,
                        combination: prev_c.combination + (1 << (count + i)),
                    }
                })
            }));
        };
    }

    values.fold(BTreeMap::new(), |mut acc, c| {
        acc.entry(c.value).or_insert(Vec::new()).push(c);
        acc
    })
}

or are you saying that that version of code is not behaving correctly?

2 Likes

Oh I can’t believe it! Is that all I needed? Thanks :slight_smile:

@steffahn

I tried out your code and got this error now:


pub fn get_combinations(all_values: &ValueSet) -> BTreeMap<Value, Vec<Combination>> {
    let simple_values = &all_values.simple;
    let comb_max = (2_usize.pow((simple_values.len()) as u32));
    let mut values = (1..comb_max).map(|v| {
        let value = get_combination_value(&v, all_values);
        Combination { value, combination: v }
    }) as Box<dyn Iterator<Item=Combination>>;

    if let Some(grouped_values) = &all_values.complex {
        let mut prevcount = simple_values.len();
        for cur_group in grouped_values {
            let count = prevcount;
            prevcount += grouped_values.len();
            values = Box::new(values.flat_map(move |prev_c| {
                cur_group.iter().enumerate().map(move |(i, v)| {
                    Combination {
                        value: prev_c.value + v,
                        combination: prev_c.combination + (1 << (count + i)),
                    }
                })
            }));
        };
    }

    values.fold(BTreeMap::new(), |mut acc, c| {
        acc.entry(c.value).or_insert(Vec::new()).push(c);
        acc
    })
}
error[E0605]: non-primitive cast: `Map<std::ops::Range<usize>, [closure@src/Comparer.rs:78:40: 81:6]>` as `Box<dyn Iterator<Item = Combination>>`
  --> src/Comparer.rs:78:22
   |
78 |       let mut values = (1..comb_max).map(|v| {
   |  ______________________^
79 | |         let value = get_combination_value(&v, all_values);
80 | |         Combination { value, combination: v }
81 | |     }) as Box<dyn Iterator<Item=Combination>>;
   | |_____________________________________________^ an `as` expression can only be used to convert between primitive types or to coerce to a specific trait object

Well, that’s because you changed something else...

pub fn get_combinations(all_values: &ValueSet) -> BTreeMap<Value, Vec<Combination>> {
    let simple_values = &all_values.simple;
    let comb_max = (2_usize.pow((simple_values.len()) as u32));
-   let mut values = Box::new((1..comb_max).map(|v| {
+   let mut values = (1..comb_max).map(|v| {
        let value = get_combination_value(&v, all_values);
        Combination { value, combination: v }
-   })) as Box<dyn Iterator<Item = Combination>>;
+   }) as Box<dyn Iterator<Item=Combination>>;

    if let Some(grouped_values) = &all_values.complex {
        let mut prevcount = simple_values.len();
        for cur_group in grouped_values {
            let count = prevcount;
            prevcount += grouped_values.len();
            values = Box::new(values.flat_map(move |prev_c| {
                cur_group.iter().enumerate().map(move |(i, v)| {
                    Combination {
                        value: prev_c.value + v,
                        combination: prev_c.combination + (1 << (count + i)),
                    }
                })
            }));
        };
    }

    values.fold(BTreeMap::new(), |mut acc, c| {
        acc.entry(c.value).or_insert(Vec::new()).push(c);
        acc
    })
}

Thanks!