When I play Rust in leetcode, the most un-happy thing for me is Rust can not easily make a recursive closure, and nearly impossible make a mutually recursive closure. So I must use a Env struct to manually wrap the captured variables, or put them all together in argument list.
I have searched the forum and found few useful result, and after some study I realize it's maybe not possible in case of borrow-checker when trying to construct a mutually recursive closure. It seems must need the language support for that.
e.g. this is a demo for get all combines for k items in 1..=n ranges:
fn make_combines(k: i32, n: i32) -> Vec<Vec<i32>> {
fn dfs(i: i32, k: i32, n: i32, cur: &mut Vec<i32>, r: &mut Vec<Vec<i32>>) {
if cur.len() == k as usize {
r.push(cur.clone());
return
}
for i in (i+1)..=(n-k+cur.len() as i32+1) {
cur.push(i);
dfs(i, k, n, cur, r);
cur.pop();
}
}
let mut r = vec![];
dfs(0, k, n, &mut vec![], &mut r);
r
}
fn main() {
println!("{:?}", make_combines(2, 4));
}
I think maybe some syntax like this may work:
fn make_combines(k: i32, n: i32) -> Vec<Vec<i32>> {
let mut cur = vec![];
let mut r = vec![];
let mut dfs = |i| {
if cur.len() == k as usize {
r.push(cur.clone());
return
}
for i in (i+1)..=(n-k+cur.len() as i32+1) {
cur.push(i);
fn(i);
cur.pop();
}
};
dfs(0);
r
}
Closures are just anonymous struct with compiler-generated Fn* trait impl. So recursive closure means self-referential struct and mutually recursive closure means mutually referential structs. Both are nightmare for lifetime analysis.
If you have a two values which reference each other, how can they be dropped in some order without producing dangling reference, even by temporarily?
We already have limited support for self reference structs with Pin API, because the struct is generated by compiler, so as this example.
We could easily make a recursive "closure" using impl block, or a manually closure object after fn_trait stabilized. So the compiler-generated version seems no problem here.
The mutually one indeed is a hard problem. But we should still just allow reference that can not reference each other, just like the normal Env struct that has several mutually reference? Maybe I'm wrong, but IMO there is at least a small set could make clear lifetime analyses.
Another proposal is to allow dynamic capture in nest fn item, this even doesn't change any syntax, just semantics. So since we have error message likes below:
error[E0434]: can't capture dynamic environment in a fn item
--> noname/2020-09-10-1.rs:5:12
|
5 | if cur.len() == k as usize {
| ^^^
|
= help: use the `|| { ... }` closure form instead
Is there any chance to allow this structure in future?
