types - 在 Rust 中构建异构类型列表

Question

我有以下 HList 的定义:

pub trait Data: Any + Debug {}
impl<T: Any + Debug> Data for T {}

/// The empty `HList`.
pub struct Nil;

/// An `HList` with `H` at position 0, and `T` as the rest of the list.
pub struct Cons<H, T> {
    head: PhantomData<H>,
    tail: PhantomData<T>,
}

/// A marker trait that `Nil` and `Cons<H, T>` satisfies.
pub trait HList {}
impl HList for Nil {}
impl<H, T: HList> HList for Cons<H, T> {}

如何通过将类型附加到末尾来构建类型？

将它们作为第一个元素插入是微不足道的:

trait Prepend<D: Data>: Sized {
    fn prepend(self, item: D) -> Cons<D, Self>;
}

impl<D: Data> Prepend<D> for Nil {
    fn prepend(self, item: D) -> Cons<D, Nil> {
        Cons {
            head: PhantomData,
            tail: PhantomData,
        }
    }
}

impl<D: Data, H, T: HList> Prepend<D> for Cons<H, T> {
    fn prepend(self, item: D) -> Cons<D, Cons<H, T>> {
        Cons {
            head: PhantomData,
            tail: PhantomData,
        }
    }
}

Playground link

但是在末尾附加元素，同时保持相同的结构似乎很难。

Nil.prepend(true).prepend(3).prepend("string") 
  -> Cons<&'static str, Cons<i32, Cons<bool, Nil>>>


Nil.push("string").push(3).push(true) 
  -> Cons<&'static str, Cons<i32, Cons<bool, Nil>>>

我知道答案是某种递归函数，它寻找列表中的最后一个 Nil 并在那里添加当前值，但我很难为与这样的递归函数。

假设我们有一个 trait Push 方法 push 将一个元素添加到 HList 最里面的括号中:

pub trait Push<?> {
    fn push(self?, el: item) -> ?;
}

如何构造它？

Answer 1

使用关联类型的递归似乎可以解决问题:

trait Append<D: Data> {
    type Result;
    fn append(self, item: D) -> Self::Result;
}

impl<D:Data> Append<D> for Nil {
    type Result = Cons<D, Nil>;
    fn append(self, item: D) -> Self::Result {
        Cons {
            head: PhantomData,
            tail: PhantomData,
        }
    }

}

impl<D:Data, H, T:HList+Append<D>> Append<D> for Cons<H,T> {
    type Result = Cons<H, <T as Append<D>>::Result>;
    fn append(self, item: D) -> Self::Result {
        Cons {
            head: PhantomData,
            tail: PhantomData,
        }
    }
}

Playground link