如何在递归数据结构中移动所有权的同时修改引用？

我想要在Rust中实现类似Lisp或Haskell的ConsList数据结构，初始代码如下：

use ConsList::*;
enum ConsList<T> {
    Empty,
    List(T, Box<ConsList<T>>),
}

impl<T> ConsList<T> {
    fn new() -> ConsList<T> {
        Empty
    }

    // 不确定self参数是否该用引用
    fn insert_first(&mut self, value: T) -> &Self {
        // 待实现
    }
    
    fn head(&mut self) -> Option<T> {
        // 待实现
    }
}

fn main() {
    let mut list_var: ConsList<i32> = ConsList::new(); // 初始化
    list_var.insert_first(2); // 第一次插入
    list_var.insert_first(1); // 第二次插入
}

期望行为 #

我希望insert_first完成以下操作：

• 创建新列表，将value放在首位
• 将旧列表移动到新列表的尾部
• 用新列表替换原变量list_var

比如初始化时list_var是Empty，第一次插入后变为List(2, Empty)；第二次插入后变为List(1, List(2, Empty))。

另外head方法需要返回列表首元素，同时将列表修改为其尾部——这样可以避免复制整个列表，节省内存和性能。

遇到的问题 #

这里存在所有权与可变引用的冲突：

• 如果不使用引用、直接转移所有权，就无法修改原变量list_var
• 如果使用可变引用，又无法直接移动旧列表（因为引用下不能转移所有权）

我尝试过用结构体包裹Box的方式，但不确定是否正确：

enum ConsListElem<T> {
    Empty,
    List(T, Box<ConsListElem<T>>),
}

pub struct ConstList<T> {
    list: Box<ConsListElem<T>>,
}

impl<T> ConstList<T> {
    pub fn cons(&mut self, value: T) -> &ConstList<T> {
        self.list = Box::new(ConsListElem::List(value, self.list));
        self
    }
}

解决方案 #

1. 修复基础ConsList的实现 #

核心是使用std::mem::replace，它允许我们在持有可变引用的情况下，取出原有值（转移所有权），同时留下一个合法的占位值。这样就能实现修改self的同时移动旧列表。

修改后的完整代码：

use ConsList::*;
enum ConsList<T> {
    Empty,
    List(T, Box<ConsList<T>>),
}

impl<T> ConsList<T> {
    fn new() -> ConsList<T> {
        Empty
    }

    fn insert_first(&mut self, value: T) -> &Self {
        // 取出旧列表，将self临时替换为Empty
        let old_list = std::mem::replace(self, Empty);
        // 创建新列表并替换回self
        *self = List(value, Box::new(old_list));
        self
    }
    
    fn head(&mut self) -> Option<T> {
        // 取出当前列表，临时替换为Empty
        let current_list = std::mem::replace(self, Empty);
        match current_list {
            Empty => {
                // 空列表，将Empty放回self，返回None
                *self = Empty;
                None
            }
            List(val, tail) => {
                // 将尾部放回self，返回首元素
                *self = *tail;
                Some(val)
            }
        }
    }
}

fn main() {
    let mut list_var: ConsList<i32> = ConsList::new();
    list_var.insert_first(2);
    list_var.insert_first(1);
    
    // 验证head方法
    assert_eq!(list_var.head(), Some(1));
    assert_eq!(list_var.head(), Some(2));
    assert_eq!(list_var.head(), None);
}

2. 结构体包裹Box的版本是可行的 #

你尝试的ConstList版本其实可以正常编译运行，因为Rust编译器允许在赋值语句中移动旧的self.list——先将旧Box的所有权转移到新的ConsListElem::List中，再将新Box赋值给self.list，编译器能确认旧的self.list不会被再次使用，因此不会触发所有权错误。

补充new方法后即可正常使用：

enum ConsListElem<T> {
    Empty,
    List(T, Box<ConsListElem<T>>),
}

pub struct ConstList<T> {
    list: Box<ConsListElem<T>>,
}

impl<T> ConstList<T> {
    pub fn new() -> Self {
        ConstList { list: Box::new(ConsListElem::Empty) }
    }
    
    pub fn cons(&mut self, value: T) -> &ConstList<T> {
        self.list = Box::new(ConsListElem::List(value, self.list));
        self
    }
}

fn main() {
    let mut list = ConstList::new();
    list.cons(2);
    list.cons(1);
    // 此时list的结构为：List(1, Box::new(List(2, Box::new(Empty))))
}

内容的提问来源于stack exchange，提问作者Atpur Rafif