This is just for sharing an idea I had for an improved trait to get items from an hlist. There is a full code below you can try on stable rust today even without specialization, but it's pretty impractical without specialization due to very limited scalability.
For context an hlist (see the hlist or frunk crates) is a heterogeneous list, and you can retrieve items from it "by type" using an appropriate trait (Find and Selector). But the trait needs an index I in order to avoid overlapping trait implementations to work.
I want to be able to use the something like the Find and Selector traits, but without the index. Specifically, I have a use case where I want a public API with trait bounds based on Find or Selector, and I do not want the index in the public API since it is just an internal implementation detail. Additionally, the index is not scalable, since you need a different index for each type you want to be able to find/select, so it is harder to make trait bounds to be able to find/select more than one type in a function.
To solve the above I wrote the below traits.
struct Hlist<H, T> {
head: H,
tail: T,
}
struct End;
// The intention is that if Self == T, then run and return result of then_branch, else run and return result else_branch
// we can see some implementation of it later
trait If<T, Then, Else> {
type Branch;
fn branch(then_branch: impl FnOnce() -> Then, else_branch: impl FnOnce() -> Else) -> Self::Branch;
}
// The intention of this Self is an Hlist, and we return a new Hlist with references to each type T in Self
// e.g. if Self is Hlist<u32, Hlist<i8, Hlist<u32, End>>>, and T = u32, then Output will be Hlist<&'a u32, Hlist<&'a u32, End>>
trait Get<'a, T> {
type Output: 'a;
fn get(&'a self) -> Self::Output;
}
impl<'a, T> Get<'a, T> for End {
type Output = End;
fn get(&'a self) -> Self::Output {
End
}
}
// looks complicated but it is simple.
// Tail needs to be Get<'a, T> so we can search the tail
// Head is If<T, Then, Else>
// if Head = T, then return an Hlist with ref to Head and search the tail, else just search the tail
// also the result of the If trait, Branch, needs 'a bound
impl<'a, T, Head: 'a, Tail> Get<'a, T> for Hlist<Head, Tail>
where
Tail: Get<'a, T>,
Head: If<T, Hlist<&'a Head, <Tail as Get<'a, T>>::Output>, <Tail as Get<'a, T>>::Output>,
<Head as If<T, Hlist<&'a Head, <Tail as Get<'a, T>>::Output>, <Tail as Get<'a, T>>::Output>>::Branch: 'a
{
type Output = <Head as If<T, Hlist<&'a Head, <Tail as Get<'a, T>>::Output>, <Tail as Get<'a, T>>::Output>>::Branch;
fn get(&'a self) -> Self::Output {
let then_branch = || Hlist { head: &self.head, tail: self.tail.get() };
let else_branch = || self.tail.get();
Head::branch(then_branch, else_branch)
}
}
// like Find or Selector, we return a reference to the type we are looking for
// This only works if the result from the above Get trait is an Hlist with a single node
// this is fine since Find or Selector only work nicely when the type in the list is unique, otherwise you would need to manually indicate the index type with is not intended
trait GetUnique<T> {
fn get_unique(&self) -> &T;
}
impl<T, List> GetUnique<T> for List
where
for <'a> List: Get<'a, T, Output = Hlist<&'a T, End>>, // Output is a single node
{
fn get_unique(&self) -> &T {
&self.get().head
}
}The above only works if we have a way to implement the If trait for every type. What we want to do needs specialization with the ability to repeat type parameters, and to use default blocks.
impl<A, B, Then, Else> If<A, Then, Else> for B {
default {
type Branch = Else;
fn branch(_then_branch: impl FnOnce() -> Then, else_branch: impl FnOnce() -> Else) -> Self::Branch {
else_branch()
}
}
}
impl<T, Then, Else> If<T, Then, Else> for T {
type Branch = Then;
fn branch(then_branch: impl FnOnce() -> Then, _else_branch: impl FnOnce() -> Else) -> Self::Branch {
then_branch()
}
}Without the above features, we can still try the above traits by manually implementing the If trait for a limited set of types that we want to put in a list. Basically, we implement the If trait for each type as compared to every other type we want to use. This means that for N types, there will be N2 If implementations. To make this somewhat doable, I made a macro that implements the If trait for a list of types where the first type is the "main" type, and the rest are compared to a the main type. I made another macro to take a list of types, and automatically build new lists so that every type can be the main type compared to every other type.
macro_rules! branch {
( $main:ty ; $($others:ty),* $(,)? ) => {
impl<Then, Else> If<$main, Then, Else> for $main {
type Branch = Then;
fn branch(then_branch: impl FnOnce() -> Then, _else_branch: impl FnOnce() -> Else) -> Self::Branch {
then_branch()
}
}
$(
impl<Then, Else> If<$main, Then, Else> for $others {
type Branch = Else;
fn branch(_then_branch: impl FnOnce() -> Then, else_branch: impl FnOnce() -> Else) -> Self::Branch {
else_branch()
}
}
)*
}
}
macro_rules! branch_combo {
// @inner main => { next types } { already processed types }
( @inner $main:ty => { } { $($already:ty , )* } ) => {
branch!( $main ; $($already , )* );
};
( @inner $main:ty => { $next:ty , $($rest:ty , )* } { $($already:ty , )* } ) => {
branch!( $main ; $next , $($rest , )* $($already , )* );
branch_combo!( @inner $next => { $($rest , )* } { $main , $($already , )* } );
};
( $first:tt , $($rest:ty),* $(,)? ) => {
branch_combo!( @inner $first => { $($rest , )* } { } );
}
}The below is a full example using the above macro. Although there may be some usefulness, it scales horribly due to the N2 implementations needs. You will notice extremely slow compile times as you add more types in branch_combo!.
#[derive(Debug, Default)]
struct A;
#[derive(Debug, Default)]
struct B;
#[derive(Debug, Default)]
struct C;
#[derive(Debug, Default)]
struct D;
trait If<T, Then, Else> {
type Branch;
fn branch(then_branch: impl FnOnce() -> Then, else_branch: impl FnOnce() -> Else) -> Self::Branch;
}
macro_rules! branch {
( $main:ty ; $($others:ty),* $(,)? ) => {
impl<Then, Else> If<$main, Then, Else> for $main {
type Branch = Then;
fn branch(then_branch: impl FnOnce() -> Then, _else_branch: impl FnOnce() -> Else) -> Self::Branch {
then_branch()
}
}
$(
impl<Then, Else> If<$main, Then, Else> for $others {
type Branch = Else;
fn branch(_then_branch: impl FnOnce() -> Then, else_branch: impl FnOnce() -> Else) -> Self::Branch {
else_branch()
}
}
)*
}
}
macro_rules! branch_combo {
( @inner $main:ty => { } { $($already:ty , )* } ) => {
branch!( $main ; $($already , )* );
};
( @inner $main:ty => { $next:ty , $($rest:ty , )* } { $($already:ty , )* } ) => {
branch!( $main ; $next , $($rest , )* $($already , )* );
branch_combo!( @inner $next => { $($rest , )* } { $main , $($already , )* } );
};
( $first:tt , $($rest:ty),* $(,)? ) => {
branch_combo!( @inner $first => { $($rest , )* } { } );
}
}
// feel free to add more types to the list until the compile times get out of hand
branch_combo!(A, B, C, D);
#[derive(Default)]
struct Hlist<H, T> {
head: H,
tail: T,
}
#[derive(Default)]
struct End;
// lets also use the macro to we can declare hlist types easier
macro_rules! hlist_ty {
() => {
$crate::End
};
( $last:path $(,)? ) => {
$crate::Hlist<$last, $crate::End>
};
( $first:path , $($rest:path),* $(,)? ) => {
$crate::Hlist<$first , hlist_ty!($($rest),*)>
};
}
trait Get<'a, T> {
type Output: 'a;
fn get(&'a self) -> Self::Output;
}
impl<'a, T> Get<'a, T> for End {
type Output = End;
fn get(&'a self) -> Self::Output {
End
}
}
// lets use these to makes code a little more readable
type IfBranch<Predicate, Condition, Then, Else> = <Predicate as If<Condition, Then, Else>>::Branch;
type GetOutput<'a, From, Out> = <From as Get<'a, Out>>::Output;
impl<'a, T, Head: 'a, Tail> Get<'a, T> for Hlist<Head, Tail>
where
Tail: Get<'a, T>,
Head: If<T, Hlist<&'a Head, GetOutput<'a, Tail, T>>, GetOutput<'a, Tail, T>>,
IfBranch<Head, T, Hlist<&'a Head, GetOutput<'a, Tail, T>>, GetOutput<'a, Tail, T>>: 'a,
{
type Output = IfBranch<Head, T, Hlist<&'a Head, GetOutput<'a, Tail, T>>, GetOutput<'a, Tail, T>>;
fn get(&'a self) -> Self::Output {
let then_branch = || Hlist { head: &self.head, tail: self.tail.get() };
let else_branch = || self.tail.get();
Head::branch(then_branch, else_branch)
}
}
trait GetUnique<T> {
fn get_unique(&self) -> &T;
}
impl<T, List> GetUnique<T> for List
where
for <'a> List: Get<'a, T, Output = Hlist<&'a T, End>>,
{
fn get_unique(&self) -> &T {
&self.get().head
}
}
fn print_c(l: impl GetUnique<C>) {
println!("{:?}", l.get_unique());
}
fn main() {
let list: hlist_ty!(A, B, C, D) = Default::default();
print_c(list);
}