在Rust中遍历"ADT“的正确方法是什么？

Question

我想实现一个非常基本的lambda reducer。出现的第一个问题是使用哪种数据类型来实现In Haskell this would be an ADT。在Rust中，使用枚举和Boxes似乎是正确的：

enum Term{
    Num(i64),
    Plus(Box<Term>, Box<Term>),
    Var(i64),
    Lam(i64, Box<Term>),
    App(Box<Term>, Box<Term>)
}

这似乎是一个很好的选择，但由于我是Rust的新手，因此我遇到的问题很可能是我选择了错误的数据类型，如果我选择了正确的数据类型表示，我的问题就解决了。如果是这样的话，请一定要让我知道！

现在我们来做一个步骤的简化。遵循Haskell代码参考，我们最终得到如下结果：

fn reduceOneStep(t: Term) -> (Term, bool) {
    match t {
        Term::Num(a) => (t, false),
        Term::Plus(t1, t2) =>
        match (*t1, *t2) {
            (Term::Num(a), Term::Num(b)) => (Term::Num(a + b), true),
            (Term::Num(a), w) =>
            match reduceOneStep(w) {
              (t, b) => if b { (Term::Plus(t1, Box::new(t)), true) } else { (Term::Plus(t1, t2), false) }
            },
            _ => (Term::Num(1), false) //ignore .. this is just to satisfy typing and totality
        },
        x => (Term::Num(1), false) //ignore .. this is just to satisfy typing and totality
    }
}

然而，这条线

(t, b) => if b { (Term::Plus(t1, Box::new(t)), true) } else { (Term::Plus(t1, t2), false) }

编译失败。原因是我“使用了移动值t1”，我并不真正理解这个错误，也不知道如何解决它。我尝试了一些其他的变种，但它们不能绕过这个问题。我的问题是:我做错了什么？

Answer 1

(附注:如果您使用Result类型而不是内部包含布尔值的元组，这可能会更好。不过，对于这个答案，我将坚持使用您编写的方式。)

如果我错了，请纠正我。

因此，如果在下面这行中，你可以让你的例子工作起来：

(t, b) => if b { (Term::Plus(t1, Box::new(t)), true) } else { (Term::Plus(t1, t2), false) }

将t1替换为Box::new(Term::Num(a))，将t2替换为Box::new(w)。那就是，加上一些缩进，就是：

(t, b) => if b {
  (Term::Plus(Box::new(Term::Num(a)), Box::new(t)), true)
} else {
  (Term::Plus(Box::new(Term::Num(a)), Box::new(w)), false)
}

但是，这也失败了，因为调用reduceOneStep(w)取得了w的所有权。这可以通过让reduceOneStep借用其参数来修复：

fn reduceOneStep(t: &Term) -> (Term, bool) {
  match t {
    &Term::Num(a) => (*t, false),
    &Term::Plus(t1, t2) =>
    match (*t1, *t2) {
      (Term::Num(a), Term::Num(b)) => (Term::Num(a + b), true),
      (Term::Num(a), w) =>
      match reduceOneStep(&w) {
        (t, b) => if b {
          (Term::Plus(Box::new(Term::Num(a)), Box::new(t)), true)
        } else {
          (Term::Plus(Box::new(Term::Num(a)), Box::new(w)), false)
        }
      },
      _ => (Term::Num(1), false) //ignore .. this is just to satisfy typing and totality
    },
    x => (Term::Num(1), false) //ignore .. this is just to satisfy typing and totality
  }
}

但这有更多的错误，cannot move out of borrowed content说，指向它返回*t的地方。解决这个问题的一种方法是对Term枚举执行#[derive(Clone)]，然后使用：

fn reduceOneStep(t: &Term) -> (Term, bool) {
  match t {
    &Term::Num(a) => (t.clone(), false),
    &Term::Plus(t1, t2) =>
    match (*t1, *t2) {
      (Term::Num(a), Term::Num(b)) => (Term::Num(a + b), true),
      (Term::Num(a), w) =>
      match reduceOneStep(&w) {
        (t, b) => if b {
          (Term::Plus(Box::new(Term::Num(a)), Box::new(t)), true)
        } else {
          (Term::Plus(Box::new(Term::Num(a)), Box::new(w.clone())), false)
        }
      },
      _ => (Term::Num(1), false) //ignore .. this is just to satisfy typing and totality
    },
    x => (Term::Num(1), false) //ignore .. this is just to satisfy typing and totality
  }
}

但是这仍然有相同的错误。哈。错误消息下面有这样的提示：help: to prevent the move, use `ref t1` or `ref mut t1` to capture value by reference。然后，在修复了一些不匹配的类型并摆弄了一些box deref和借入之后，我终于让它起作用了：

fn reduceOneStep(t: &Term) -> (Term, bool) {
  match t {
    &Term::Num(a) => (t.clone(), false),
    &Term::Plus(ref t1, ref t2) =>
    match (&**t1, &**t2) {
      (&Term::Num(a), &Term::Num(b)) => (Term::Num(a + b), true),
      (&Term::Num(a), w) =>
      match reduceOneStep(&w) {
        (t, b) => if b {
          (Term::Plus(Box::new(Term::Num(a)), Box::new(t)), true)
        } else {
          (Term::Plus(Box::new(Term::Num(a)), Box::new(w.clone())), false)
        }
      },
      _ => (Term::Num(1), false) //ignore .. this is just to satisfy typing and totality
    },
    x => (Term::Num(1), false) //ignore .. this is just to satisfy typing and totality
  }
}

我现在是铁锈的初学者，所以如果有人能帮助我理解它的工作原理，我将不胜感激。