我正在尝试从F#移植一个小基准到Rust.F#代码如下所示:
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个最近邻壳.我在博士期间使用类似的东西来研究无定形材料.
我花了很多时间尝试并且没有将它移植到Rust.我设法让一个版本工作,但只能通过手动内联闭包并将递归转换为带有本地变量的循环(yuk!).
我尝试写这样的iterNeighbors函数:
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));
}
我认为这是一个接受闭包的函数(它本身接受一对并返回单位)和一对并返回单位.我似乎必须加倍支架:这是正确的吗？
我尝试编写这样的递归版本:
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.
我想我正在努力让参数的生命周期正确,因为它们在递归调用中被旋转.如果我想s2在returns 之前被解除分配并且我想s1在返回时或者在递归调用中生存,我应该如何注释生命周期？
调用者看起来像这样:
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带有可变本地的循环:
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;
}
如果我手动内联闭包,这是有效的,但我无法弄清楚如何调用闭包.理想情况下,我想在这里静态发送.
该main功能则是:
fn main() {
let s = nth(2000, (0, 0));
println!("{}", s.len());
}
那么......我做错了什么？:-)
此外,我只HashSet在F#中使用,因为我认为Rust不提供纯粹的功能Set和有效的集合理论操作(并集,交集和差异).我认为这是正确的吗？
我似乎必须加倍支架:这是正确的吗？
否:双括号是因为你选择使用元组并调用一个带元组的函数需要先创建元组,但是可以有一个带有多个参数的闭包,比如F: Fn(i32, i32).也就是说,可以将该函数编写为:
fn iterNeighbors<F>(i: i32, j: i32, f: F)
where
F: Fn(i32, i32),
{
f(i - 1, j);
f(i + 1, j);
f(i, j - 1);
f(i, j + 1);
}
但是,似乎保留元组对于这种情况是有意义的.
我想我正在努力让参数的生命周期正确,因为它们在递归调用中被旋转.如果我希望s2在返回之前被释放并且我希望s1在返回时或者在递归调用中生存时,我应该如何注释生命周期？
不需要引用(因此不需要生命周期),只需直接传递数据:
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 {
iterNeighbors(p, |p| {
if !(s1.contains(&p) || s2.contains(&p)) {
s0.insert(p);
}
})
}
drop(s2); // guarantees timely deallocation
return nthLoop(n - 1, s0, s1);
}
}
这里的关键是你可以按价值做所有事情,价值传递的东西当然会保持他们的价值观.
但是,这无法编译:
error[E0387]: cannot borrow data mutably in a captured outer variable in an `Fn` closure
--> src/main.rs:21:21
|
21 | s0.insert(p);
| ^^
|
help: consider changing this closure to take self by mutable reference
--> src/main.rs:19:30
|
19 | iterNeighbors(p, |p| {
| ______________________________^
20 | | if !(s1.contains(&p) || s2.contains(&p)) {
21 | | s0.insert(p);
22 | | }
23 | | })
| |_____________^
也就是说,闭包试图改变它捕获的值(s0),但Fn闭包特征不允许这样做.可以以更灵活的方式(共享时)调用该特征,但是这会对封闭在内部执行的操作施加更多限制.(如果你有兴趣,我已经写了更多关于这个)
幸运的是,有一个简单的解决方法:使用FnMuttrait,这要求只有在对其具有唯一访问权限时才能调用闭包,但允许内部变更.
fn iterNeighbors<F>((i, j): (i32, i32), mut f: F)
where
F: FnMut((i32, i32)),
{
f((i - 1, j));
f((i + 1, j));
f((i, j - 1));
f((i, j + 1));
}
调用者看起来像这样:
值也可以在这里工作:在这种情况下返回一个引用将返回一个指针s0,该指针生成在函数返回时被销毁的堆栈帧.也就是说,引用指向死数据.
该修复程序不使用引用:
fn nth(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> {
let s0 = HashSet::new();
let mut s1 = HashSet::new();
s1.insert(p);
return nthLoop(n, s1, s0);
}
如果我手动内联闭包,但是我无法弄清楚如何调用闭包,这是有效的.理想情况下,我想在这里静态发送.
(我不明白这意味着什么,包括你遇到麻烦的编译错误信息可以帮助我们.)
另外,我只在F#中使用了HashSet,因为我认为Rust不提供具有有效集合理论操作(并集,交集和差异)的纯函数集.我认为这是正确的吗？
具体取决于您想要什么,不,例如,HashSet并且BTreeSet提供各种集合理论操作作为返回迭代器的方法.
一些小点:
s0.clear(),但是,通过传递s2重用而不是丢弃它,可以通过递归版本实现相同的好处.while循环可for _ in 0..nfoo(x, |y| bar(y + 1))而不是foo(&|y| bar(y + 1), x))该return关键字是没有必要的后返回(如果;被省略):
fn nth(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> {
let s0 = HashSet::new();
let mut s1 = HashSet::new();
s1.insert(p);
nthLoop(n, s1, s0)
}
我认为这是一个接受闭包的函数(它本身接受一对并返回单位)和一对并返回单位.我似乎必须加倍支架:这是正确的吗？
你需要双括号,因为你将2元组传递给闭包,它与原始的F#代码相匹配.
我想我正在努力让参数的生命周期正确,因为它们在递归调用中被旋转.如果我希望s2在返回之前被释放并且我希望s1在返回时或者在递归调用中生存时,我应该如何注释生命周期？
问题是HashSet当你应该直接使用HashSets 时,你正在使用对s的引用.你的签名nthLoop已经是正确的; 你只需要删除几次&.
要解除分配s2,你可以写drop(s2).请注意,Rust没有保证尾调用,因此每次递归调用仍然会占用一些堆栈空间(您可以看到该mem::size_of函数有多少),但drop调用将清除堆上的数据.
调用者看起来像这样:
再一次,你只需要删除&这里的.
请注意,我还没有打扰到iterNeighbors的调用.
如果我手动内联闭包,但是我无法弄清楚如何调用闭包,这是有效的.理想情况下,我想在这里静态发送.
有三种类型的防锈封闭的:Fn,FnMut和FnOnce.他们的self论点类型不同.区别很重要,因为它限制了允许关闭的内容以及调用者如何使用闭包.Rust书中有一章关于闭包,已经很好地解释了这一点.
你的关闭需要改变s0.但是,iterNeighbors定义为期望Fn关闭.你的闭包不能实现,Fn因为Fn接收&self,但变异s0,你需要&mut self.iterNeighbors不能使用FnOnce,因为它需要不止一次调用闭包.因此,您需要使用FnMut.
此外,没有必要通过引用传递闭包iterNeighbors.你可以按值传递它; 每次对闭包的调用都只会借用闭包,而不是消耗它.
另外,我只在F#中使用了HashSet,因为我认为Rust不提供具有有效集合理论操作(并集,交集和差异)的纯函数集.我认为这是正确的吗？
标准库中没有纯粹的功能集实现(也许在crates.io上有一个？).虽然Rust包含函数式编程,但它还利用其所有权和借用系统来使命令式编程更安全.函数集可能会使用某种形式的引用计数或垃圾回收来强制使用集合来共享项目.
但是,HashSet是否实现了集合理论操作.有使用它们两种方式:迭代器(difference,symmetric_difference,intersection,union),该懒惰地生成序列,或运营商(|,&,^,-,如在所列出的特征实现为HashSet),其产生包含的值的克隆从源集新套.
这是工作代码:
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());
}