Rust 中与闭包和生命周期作斗争

我正在尝试将一些基准测试从 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 yet.

我认为我正在努力使参数的生命周期正确，因为它们在递归调用中进行轮换。如果我愿意，我应该如何注释生命周期s2在之前被释放return我想要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;
}

如果我手动内联闭包，这是可行的，但我不知道如何调用闭包。理想情况下，我希望在这里进行静态调度。

The main那么函数是：

fn main() {
    let s = nth(2000, (0, 0));
    println!("{}", s.len());
}

那么...我做错了什么？ :-)

另外，我只用过HashSet在 F# 中，因为我认为 Rust 不提供纯函数式Set具有高效的集合论运算（并集、交集和差集）。我的假设正确吗？

我认为这是一个接受闭包（本身接受一对并返回单位）和一对并返回单位的函数。我似乎必须把事情加双括号：这是正确的吗？

您需要双括号，因为您要向闭包传递一个 2 元组，它与您的原始 F# 代码相匹配。

我认为我正在努力使参数的生命周期正确，因为它们在递归调用中进行轮换。如果我希望 s2 在返回之前被释放并且我希望 s1 在返回时或进入递归调用时生存，我应该如何注释生命周期？

问题是您正在使用对HashSet当你应该使用HashSet直接。您的签名nthLoop已经是正确的；你只需要删除一些出现的&.

解除分配s2， 你可以写drop(s2)。请注意，Rust 没有保证尾部调用，因此每个递归调用仍会占用一点堆栈空间（您可以使用mem::size_of https://doc.rust-lang.org/std/mem/fn.size_of.html函数），但是drop调用将清除堆上的数据。

调用者看起来像这样：

同样，您只需删除&'s here.

请注意，我什至还没有考虑对 iterNeighbors 的调用。

---

如果我手动内联闭包，这是可行的，但我不知道如何调用闭包。理想情况下，我希望在这里进行静态调度。

Rust 中有三种类型的闭包：Fn https://doc.rust-lang.org/stable/std/ops/trait.Fn.html, FnMut https://doc.rust-lang.org/stable/std/ops/trait.FnMut.html and FnOnce https://doc.rust-lang.org/stable/std/ops/trait.FnOnce.html。它们的类型不同self争论。这种区别很重要，因为它对允许闭包执行的操作以及调用者如何使用闭包施加了限制。 Rust 书中有关于闭包的一章 https://doc.rust-lang.org/stable/book/closures.html这已经很好地解释了这一点。

你的闭包需要改变s0。然而，iterNeighbors被定义为期望Fn关闭。你的关闭无法执行Fn因为Fn收到&self，但要变异s0， 你需要&mut self. iterNeighbors不能用FnOnce，因为它需要多次调用闭包。因此，您需要使用FnMut.

另外，没有必要通过引用来传递闭包iterNeighbors。你可以直接按值传递；对闭包的每次调用只会借用闭包，而不会消耗它。

另外，我只在 F# 中使用 HashSet，因为我假设 Rust 不提供具有高效集合论操作（并集、交集和差集）的纯函数集。我的假设正确吗？

标准库中没有纯函数集实现（也许有一个）crates.io https://crates.io/？）。虽然 Rust 支持函数式编程，但它也利用其所有权和借用系统来使命令式编程更安全。功能集可能会强制使用某种形式的引用计数或垃圾收集，以便跨集共享项目。

然而，HashSet https://doc.rust-lang.org/std/collections/struct.HashSet.html确实实现了集合论运算。有两种使用它们的方法：迭代器（difference https://doc.rust-lang.org/std/collections/struct.HashSet.html#method.difference, symmetric_difference https://doc.rust-lang.org/std/collections/struct.HashSet.html#method.symmetric_difference, intersection https://doc.rust-lang.org/std/collections/struct.HashSet.html#method.intersection, union https://doc.rust-lang.org/std/collections/struct.HashSet.html#method.union)，它延迟生成序列，或运算符 (|, &, ^, -，如所列特征实现HashSet https://doc.rust-lang.org/std/collections/struct.HashSet.html#implementations），它生成包含源集中值的克隆的新集。

这是工作代码：

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());
}