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

Question

我尝试实现

ConsList

数据结构，它来自 Lisp 或 Haskell 等函数范式语言。这里有一些片段：

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

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

    // I don't know whether to use & or not at self parameter
    fn insert_first(&mut self, value: T) -> &Self {
        // unkown implementation
    }
    
    fn head(&mut self) -> Option<T> {
        // unkown implementation
    }
}

fn main() {
    let mut list_var: ConsList<i32> = ConsList::new(); // Initiate
    list_var.insert_first(2); // First insert
    list_var.insert_first(1); // Second insert
}

我希望

insert_first

函数的行为如下：

1. 在新列表元组的第一个位置使用

   value

   创建新列表
2. 将值移至新列表的尾部
3. 用新列表替换所有者变量（

   list_var

   ）

例如，在启动时，我们有

Empty

变量的

list_var

值。然后在第一次插入时，它将创建新值

List(2, Empty)

，其中

2

从

value

移动，并且

Empty

在突变之前从旧列表移动，并且我们将

self

变量突变到新列表。换句话说，我们改变

list_var

变量。为了更深入，这里是我在第二次插入时一步一步的意思：

1. 将

   list_var

   (

   List(2, Empty)

   ) 移至

   self

   方法中的参数

   insert_first

2. 将

   1

   移至

   value

   方法中的参数

   insert_first

3. 创建新列表，并将

   value

   和

   self

   移至新列表，

   List(3, List(2, Empty))

4. 用新列表改变

   self

   ，因此

   list_var

   变量也将成为新列表

问题就在这里，我们只能：

• 在没有参考的情况下转移所有权（我们无法变异

  list_var

  ）
• 借用但不能移动（我们不能将旧列表移动到新列表）

据我所知，我们无法在能够通过引用进行变异的同时转移所有权。这是有用的，有一些原因。方法

head

将返回列表的第一个元素并将列表变异为尾部（我知道变异不是函数式编程中的事情，但这将节省复制新列表的存储空间和性能）。此方法需要能够变异

self

，移动第一个元素以返回值，并将列表尾部的所有权移动到

self

。

我尝试使用盒子进行间接寻址，但我仍然无法移动

self.list

，因为它位于引用后面

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
    }
}

Answer 1

您可以使用 std::mem::replace 修改可变引用后面的内容并返回旧值。因此，在

insert_first

中，您可以首先将

self

替换为

Empty

变体，然后创建新的

List

并将其分配给

self

。

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

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

    fn insert_first(&mut self, value: T) -> &mut Self {
        match self {
            Self::Empty => {
                *self = Self::List(value, Box::new(Self::new()))
            }
            Self::List(_, _) => {
                let old = std::mem::replace(self, Self::new());
                *self = Self::List(value, Box::new(old));
            }
        }
        self
    }
    
    fn head(&self) -> Option<&T> {
        match self {
            Self::Empty => None,
            Self::List(head, _) => Some(head),
        }
    }
}

fn main() {
    let mut list_var: ConsList<i32> = ConsList::new(); // Initiate
    assert_eq!(list_var.head(), None);
    list_var.insert_first(2); // First insert
    assert_eq!(list_var.head(), Some(&2));
    list_var.insert_first(1); // Second insert
    assert_eq!(list_var.head(), Some(&1));
}