在 Rust 中挣扎于闭包和生命周期 [英] Struggling with closures and lifetimes in Rust
问题描述
我正在尝试将一些基准测试从 F# 移植到 Rust.F# 代码如下所示:
I'm trying to port a little benchmark from F# to Rust. The F# code looks like this:
let inline iterNeighbors f (i, j) =
f (i-1, j)
f (i+1, j)
f (i, j-1)
f (i, j+1)
let rec nthLoop n (s1: HashSet<_>) (s2: HashSet<_>) =
match n with
| 0 -> s1
| n ->
let s0 = HashSet(HashIdentity.Structural)
let add p =
if not(s1.Contains p || s2.Contains p) then
ignore(s0.Add p)
Seq.iter (fun p -> iterNeighbors add p) s1
nthLoop (n-1) s0 s1
let nth n p =
nthLoop n (HashSet([p], HashIdentity.Structural)) (HashSet(HashIdentity.Structural))
(nth 2000 (0, 0)).Count
它从潜在无限图中的初始顶点计算第 n 个最近邻壳.我在博士期间使用了类似的东西来研究无定形材料.
It computes the nth-nearest neighbor shells from an initial vertex in a potentially infinite graph. I used something similar during my PhD to study amorphous materials.
我花了很多时间尝试将其移植到 Rust，但未能成功.我设法让一个版本正常工作，但只能通过手动内联闭包并将递归转换为具有本地可变变量的循环(yuk！).
I've spent many hours trying and failing to port this to Rust. I have managed to get one version working but only by manually inlining the closure and converting the recursion into a loop with local mutables (yuk!).
我尝试像这样编写 iterNeighbors 函数:
I tried writing the iterNeighbors function like this:
use std::collections::HashSet;
fn iterNeighbors<F>(f: &F, (i, j): (i32, i32)) -> ()
where
F: Fn((i32, i32)) -> (),
{
f((i - 1, j));
f((i + 1, j));
f((i, j - 1));
f((i, j + 1));
}
我认为这是一个接受闭包(它本身接受一对并返回单位)和一对并返回单位的函数.我似乎必须用双括号括起来:这是正确的吗?
I think that is a function that accepts a closure (that itself accepts a pair and returns unit) and a pair and returns unit. I seem to have to double bracket things: is that correct?
我试着写一个这样的递归版本:
I tried writing a recursive version like this:
fn nthLoop(n: i32, s1: HashSet<(i32, i32)>, s2: HashSet<(i32, i32)>) -> HashSet<(i32, i32)> {
if n == 0 {
return &s1;
} else {
let mut s0 = HashSet::new();
for &p in s1 {
if !(s1.contains(&p) || s2.contains(&p)) {
s0.insert(p);
}
}
return &nthLoop(n - 1, s0, s1);
}
}
请注意，我什至还没有为调用 iterNeighbors 而烦恼.
Note that I haven't even bothered with the call to iterNeighbors yet.
我想我正在努力使参数的生命周期正确，因为它们在递归调用中轮换.如果我希望 s2 在 returns 之前被释放并且我希望 s1 在返回或进入时存活，我应该如何注释生命周期递归调用?
I think I'm struggling to get the lifetimes of the arguments correct because they are rotated in the recursive call. How should I annotate the lifetimes if I want s2 to be deallocated just before the returns and I want s1 to survive either when returned or into the recursive call?
调用者看起来像这样:
fn nth<'a>(n: i32, p: (i32, i32)) -> &'a HashSet<(i32, i32)> {
let s0 = HashSet::new();
let mut s1 = HashSet::new();
s1.insert(p);
return &nthLoop(n, &s1, s0);
}
我放弃了，把它写成一个 while 循环，用可变的局部变量代替:
I gave up on that and wrote it as a while loop with mutable locals instead:
fn nth<'a>(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> {
let mut n = n;
let mut s0 = HashSet::new();
let mut s1 = HashSet::new();
let mut s2 = HashSet::new();
s1.insert(p);
while n > 0 {
for &p in &s1 {
let add = &|p| {
if !(s1.contains(&p) || s2.contains(&p)) {
s0.insert(p);
}
};
iterNeighbors(&add, p);
}
std::mem::swap(&mut s0, &mut s1);
std::mem::swap(&mut s0, &mut s2);
s0.clear();
n -= 1;
}
return s1;
}
如果我手动内联闭包，这会起作用，但我不知道如何调用闭包.理想情况下，我希望在这里进行静态调度.
This works if I inline the closure by hand, but I cannot figure out how to invoke the closure. Ideally, I'd like static dispatch here.
main 函数就是:
fn main() {
let s = nth(2000, (0, 0));
println!("{}", s.len());
}
所以……我做错了什么?:-)
So... what am I doing wrong? :-)
此外，我只在 F# 中使用了 HashSet，因为我认为 Rust 没有提供具有高效集合论操作(并集、交集和差集)的纯函数式 Set).我的假设正确吗?
Also, I only used HashSet in the F# because I assume Rust doesn't provide a purely functional Set with efficient set-theoretic operations (union, intersection and difference). Am I correct in assuming that?
推荐答案
我认为这是一个接受闭包(它本身接受一对并返回单位)和一对并返回单位的函数.我似乎必须用双括号括起来:这是正确的吗?
I think that is a function that accepts a closure (that itself accepts a pair and returns unit) and a pair and returns unit. I seem to have to double bracket things: is that correct?
您需要双括号，因为您将一个 2 元组传递给闭包，它与您的原始 F# 代码相匹配.
You need the double brackets because you're passing a 2-tuple to the closure, which matches your original F# code.
我想我正在努力使参数的生命周期正确，因为它们在递归调用中轮换.如果我希望 s2 在返回之前被解除分配并且我希望 s1 在返回或进入递归调用时继续存在，我应该如何注释生命周期?
I think I'm struggling to get the lifetimes of the arguments correct because they are rotated in the recursive call. How should I annotate the lifetimes if I want s2 to be deallocated just before the returns and I want s1 to survive either when returned or into the recursive call?
问题是您使用了对 HashSets 的引用，而您应该直接使用 HashSets.您对 nthLoop 的签名已经正确；您只需要删除一些出现的 &.
The problem is that you're using references to HashSets when you should just use HashSets directly. Your signature for nthLoop is already correct; you just need to remove a few occurrences of &.
要释放s2，你可以写drop(s2).请注意，Rust 没有保证尾调用，因此每次递归调用仍会占用一些堆栈空间(您可以使用 mem::size_of 函数)，但 drop 调用将清除堆.
To deallocate s2, you can write drop(s2). Note that Rust doesn't have guaranteed tail calls, so each recursive call will still take a bit of stack space (you can see how much with the mem::size_of function), but the drop call will purge the data on the heap.
调用者看起来像这样:
同样，您只需删除此处的 &.
Again, you just need to remove the &'s here.
请注意，我什至还没有为调用 iterNeighbors 而烦恼.
Note that I haven't even bothered with the call to iterNeighbors yet.
如果我手动内联闭包，但我不知道如何调用闭包，这会起作用.理想情况下，我希望在这里进行静态调度.
This works if I inline the closure by hand but I cannot figure out how to invoke the closure. Ideally, I'd like static dispatch here.
Rust 中有三种类型的闭包:Fn, FnMut 和 FnOnce.它们的不同在于 self 参数的类型.区别很重要，因为它限制了闭包可以做什么以及调用者如何使用闭包.Rust 书中的一章关于闭包 已经很好地解释了这一点.
There are three types of closures in Rust: Fn, FnMut and FnOnce. They differ by the type of their self argument. The distinction is important because it puts restrictions on what the closure is allowed to do and on how the caller can use the closure. The Rust book has a chapter on closures that already explains this well.
你的闭包需要改变 s0.然而，iterNeighbors 被定义为期待一个 Fn 闭包.你的闭包不能实现 Fn 因为 Fn 接收 &self，但是要改变 s0，你需要 &mut self.iterNeighbors 不能使用 FnOnce，因为它需要多次调用闭包.因此，您需要使用FnMut.
Your closure needs to mutate s0. However, iterNeighbors is defined as expecting an Fn closure. Your closure cannot implement Fn because Fn receives &self, but to mutate s0, you need &mut self. iterNeighbors cannot use FnOnce, since it needs to call the closure more than once. Therefore, you need to use FnMut.
此外，没有必要通过引用 iterNeighbors 来传递闭包.你可以只按值传递它；每次调用闭包只会借用闭包，不会消耗它.
Also, it's not necessary to pass the closure by reference to iterNeighbors. You can just pass it by value; each call to the closure will only borrow the closure, not consume it.
此外，我只在 F# 中使用了 HashSet，因为我认为 Rust 不提供具有高效集合论操作(并集、交集和差集)的纯函数集.我的假设正确吗?
Also, I only used HashSet in the F# because I assume Rust doesn't provide a purely functional Set with efficient set-theoretic operations (union, intersection and difference). Am I correct in assuming that?
标准库中没有纯函数集实现(也许 crates.io 上有一个?).虽然 Rust 接受函数式编程，但它也利用其所有权和借用系统来使命令式编程更安全.功能集可能会强制使用某种形式的引用计数或垃圾收集，以便跨集共享项目.
There's no purely functional set implementation in the standard library (maybe there's one on crates.io?). While Rust embraces functional programming, it also takes advantage of its ownership and borrowing system to make imperative programming safer. A functional set would probably impose using some form of reference counting or garbage collection in order to share items across sets.
然而，HashSet 确实实现了集合论操作.有两种使用方法:迭代器(差异、<代码>对称差异，intersection, union), 懒惰地生成序列，或者操作符 (|, &, ^>、-，如HashSet 的 >trait 实现)，它产生包含从值的克隆的新集合源集.
However, HashSet does implement set-theoretic operations. There are two ways to use them: iterators (difference, symmetric_difference, intersection, union), which generate the sequence lazily, or operators (|, &, ^, -, as listed in the trait implementations for HashSet), which produce new sets containing clones of the values from the source sets.
这是工作代码:
use std::collections::HashSet;
fn iterNeighbors<F>(mut f: F, (i, j): (i32, i32)) -> ()
where
F: FnMut((i32, i32)) -> (),
{
f((i - 1, j));
f((i + 1, j));
f((i, j - 1));
f((i, j + 1));
}
fn nthLoop(n: i32, s1: HashSet<(i32, i32)>, s2: HashSet<(i32, i32)>) -> HashSet<(i32, i32)> {
if n == 0 {
return s1;
} else {
let mut s0 = HashSet::new();
for &p in &s1 {
let add = |p| {
if !(s1.contains(&p) || s2.contains(&p)) {
s0.insert(p);
}
};
iterNeighbors(add, p);
}
drop(s2);
return nthLoop(n - 1, s0, s1);
}
}
fn nth(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> {
let mut s1 = HashSet::new();
s1.insert(p);
let s2 = HashSet::new();
return nthLoop(n, s1, s2);
}
fn main() {
let s = nth(2000, (0, 0));
println!("{}", s.len());
}
这篇关于在 Rust 中挣扎于闭包和生命周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
