树/项上的递归替换

Question

下面我用变量定义了树状术语，这些术语将被方法中的术语替换

substitution

。 我有两次尝试，都编译但产生了错误的结果。

除了这两次尝试之外，我还看到了使用

RC<RefCell<T>>

作为子节点的二叉树实现，但我无法成功应用它，而且我不确定是否应该使用它。

尝试1

由于映射

(v,t)

已被删除，因此仅替换第一个变量

v

。 我尝试使用

valuation.get

（允许估值不可变），但这给了我一个术语的参考。 然后取消引用该引用不起作用，克隆/复制似乎也不起作用。

use std::collections::{HashMap};
use std::hash::{Hash};

#[derive(Debug)]
enum Term {
    Variable(u32),
    Operation(u32, Vec<Term>),
}

impl Term {
    fn substitute(self: Term, valuation: &mut HashMap<u32, Term>) -> Term {
        match self {
            Term::Variable(v) => {
                match valuation.remove(&v) {
                    None => { self } // variable not mapped by valuation
                    Some(t) => { t } // variable replaced according to valuation
                }
            }
            Term::Operation(op, args) => {
                // apply substitute recursively
                let mut updated: Vec<Term> = Vec::new();
                for t in args {
                    updated.push(t.substitute(valuation))
                }
                Term::Operation(op, updated)
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_bad_add() {
        let term = Term::Operation(1, vec![Term::Variable(2), Term::Variable(2)]);
        let mut map = HashMap::new();
        map.insert(2, Term::Operation(3, vec![]));
        let result = term.substitute(&mut map);
        println!("{:?}", result);
        // prints: Operation(1, [Operation(3, []), Variable(2)])
        // expected: Operation(1, [Operation(3, []), Operation(3, [])])
    }
}

尝试2

在这里，我尝试模仿我在其他地方看到的解引用方法，但（至少）递归部分不起作用

use std::collections::{HashMap};
use std::hash::{Hash};

#[derive(Debug)]
enum Term {
    Variable(u32),
    Operation(u32, Vec<Term>),
}

impl Term {
    fn substitute(self: &mut Term, valuation: &mut HashMap<u32, Term>) -> () {
        match self {
            Term::Variable(v) => {
                match valuation.remove(&v) {
                    None => { () } // variable not mapped by valuation
                    Some(t) => { *self=t } // variable replaced according to valuation
                }
            }
            Term::Operation(op, args) => {
                // apply substitute recursively
                let mut updated: Vec<Term> = Vec::new();
                for t in args {
                    (*t).substitute(valuation)
                }
                *self=Term::Operation(*op, updated)
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_bad_add() {
        let mut term = Term::Operation(1, vec![Term::Variable(2), Term::Variable(2)]);
        let mut map = HashMap::new();
        map.insert(2, Term::Operation(3, vec![]));
        let result =  term.substitute(&mut map);
        println!("{:?}", term);
        // prints: Operation(1, [])
        // expected: Operation(1, [Operation(3, []), Operation(3, [])])
    }
}

Answer 1

错误来自于您在读取赋值时删除了它（您调用的方法名为

remove

，所以这并不奇怪...），因此第二次尝试读取变量 2 的赋值时，已经没有了。将

remove

替换为

get

以使其正常工作。