Constructing Hetereogenous Type Lists in Rust

Question

I have the following definition of 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> {}

How would I construct the types by appending them to the end?

Inserting them as the first element is trivial:

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

But appending elements on the end, while maintaining same structure seems hard.

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

I know the answer is some kind of recursive function, that seeks to the last Nil in the list and adds the current value there, but I have difficulty defining a function for the trait that works with such a recursive function.

Assuming we have a trait Push with the method push that adds an element into the HList in the innermost bracket:

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

How would one construct it?

Answer 1

Recursion on using associated types seems to do the trick:

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