不关心拥有子结构的递归数据类型

Question

我经常想在 Rust 中定义递归数据类型。我们需要某种程度的间接来避免拥有无限大小的类型。经典的解决方案是使用 Box (playground):

enum IntList {
    Empty,
    Cons(i32, Box<IntList>),
}

我遇到的问题是它要求列表拥有自己的尾巴。这意味着您不能 space 在共享尾部的两个列表之间共享，因为两者都想拥有它。您可以使用借来的参考 (playground):

enum IntList<'a> {
    Empty,
    Cons(i32, &'a IntList<'a>),
}

但是很难创建列表，因为它不允许拥有自己的尾巴。

有没有办法让列表不关心它是否拥有尾部？这样我就可以让一个列表拥有尾部而另一个列表引用与它的尾巴相同的列表。

我的尝试

我的第一个想法是使用 Cow 来达到这个目的，但我无法让它工作。这是我试过的 (playground):

#[derive(Clone)]
enum IntList<'a> {
    Empty,
    Cons(i32, Cow<'a, IntList<'a>),
}

但失败并出现错误

error[E0275]: overflow evaluating the requirement `IntList<'a>: std::marker::Sized`
 --> src/main.rs:8:13
  |
8 |   Cons(i32, Cow<'a, IntList<'a>>),
  |             ^^^^^^^^^^^^^^^^^^^^
  |
  = note: required because of the requirements on the impl of `std::borrow::ToOwned` for `IntList<'a>`
  = note: required because it appears within the type `std::borrow::Cow<'a, IntList<'a>>`
  = note: no field of an enum variant may have a dynamically sized type

Answer 1

我创建了一个类似于 Cow 的数据类型，我称之为 Cowish。如果已经有这样的东西，请告诉我！

pub enum Cowish<'a, T, O>
where
    T: 'a,
{
    Borrowed(&'a T),
    Owned(O),
}

impl<'a, T, O> Borrow<T> for Cowish<'a, T, O>
where
    T: 'a,
    O: Borrow<T>,
{
    fn borrow(&self) -> &T {
        match self {
            Borrowed(b) => b,
            Owned(o) => o.borrow(),
        }
    }
}

impl<'a, T, O> Cowish<'a, T, O>
where
    T: ToOwned<Owned=O> + 'a,
    O: Borrow<T>,
{
    pub fn into_owned(self) -> O {
        match self {
            Borrowed(b) => b.to_owned(),
            Owned(o) => o,
        }
    }
}

使用它，我可以做我想做的事：

enum IntList<'a> {
    Empty,
    Cons(i32, Cowish<'a, IntList<'a>, Box<IntList<'a>>>),
}

可以找到更大的示例 here。

Answer 2

这可能太旧了，但只是为了记录，如果你想做一个链表你可以使用std::rc::Rc。它就像 Box，但是您可以对一个对象有多个引用。唯一需要注意的是，一旦包含在 Rc 中，您就不能更改列表。这是来自 rust book:

的示例

enum List {
    Cons(i32, Rc<List>),
    Nil,
}

use crate::List::{Cons, Nil};
use std::rc::Rc;

fn main() {
    let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil))))); // [10, 5]
    let b = Cons(3, Rc::clone(&a)); // [10, 5, 3]
    let c = Cons(4, Rc::clone(&a)); // [10, 5, 4]
}

不关心拥有子结构的递归数据类型

Recursive data type that doesn't care about owning substructure

ownership

rust

borrowing

我的尝试