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

Question

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

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

我遇到的问题是它要求列表拥有自己的尾部。这意味着您不能在共享尾部的两个列表之间共享空间，因为两者都想拥有它。您可以使用借来的引用资料 ( 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 .