[Question] Treating an HList like a set/map?

[kitlith]

Say I have a type HList![A, B, A, ...]. Is there a way to obtain a type HList![A, B, ...] or HList![B, A, ...] in a generic fashion?

Alternatively, say I have two HList types. HList![A] + HList![B] would produce HList![A, B], while HList![A, B] + HList![A, C] would produce HList![A, B, C].

In case this is an XY Problem, my usecase looks somewhat like this:

trait SomeTrait {
    type Ctx;
    fn do_something(ctx: Self::Ctx);
}

struct A {}
struct B {}
struct Parent<T: SomeTrait> {
    a: A,
    b: T
}

impl SomeTrait for A {
    type Ctx = HList![u8];
    fn do_something(ctx: Self::Ctx) -> A {
        let _: &u8 = ctx.get();
        unimplemented!();
    }
}

impl SomeTrait for B {
    type Ctx = HList![u8, String];
    fn do_something(ctx: Self::Ctx) {
        let _: &u8 = ctx.get();
        let _: &String = ctx.get();
        unimplemented!();
    }
}

impl<T> SomeTrait for Parent<T> {
    type Ctx = /* some combination of A::Ctx and <T as SomeTrait>::Ctx ??? */;
    fn do_something(ctx: Self::Ctx) {
        A::do_something(ctx.clone().sculpt());
        <T as SomeTrait>::do_something(ctx.sculpt());
    }
}

I know this is possible if I make SomeTrait generic on Ctx instead of making it an associated type, but I figured I'd look into methods that require less monomorphization.

[ExpHP]

Alternatively, say I have two HList types. HList![A] + HList![B] would produce HList![A, B], while HList![A, B] + HList![A, C] would produce HList![A, B, C].

I believe this would be very difficult to do, perhaps impossible within rust's trait system.

To see why, let's consider a closely related but simpler example: Suppose that we wish to define a trait Has<A> which is implemented by any HList that contains at least one A. If we were to naively write some impls for this trait:

trait Has<A> {}

// base case
impl<A, T> Has<A> for HCons<A, T> {}
// recursive case
impl<A, H, T> Has<A> for HCons<H, T> where T: Has<A> {}

The problem with the above impls is that they conflict! Rust won't allow these impls to coexist because a type like Hlist![A, A, B] would satisfy both of them. (this would require some form of "lattice rule" specialization, where we would be allowed to write an impl for the overlapping case of impl<A, T> Has<A> for HCons<A, T> where T: Has<A>; and I don't think there are any plans to add such a feature to rust)

The way that frunk generally overcomes this sort of problem is by introducing an "index type." This is a fake type parameter that makes it possible to differentiate between the impls:

trait Has<A, Index> {}

// If you are familiar with Peano integers, these are basically Zero and Succ(N).
enum Here {}
struct There<N>(N);

impl<A, T> Has<A, Here> for HCons<A, T> {}

impl<A, H, T, N> Has<A, There<N>> for HCons<H, T> where T: Has<A, N> {}

What happens now is, Hlist![A, B, C] implements Has<A, Here>, while Hlist![B, A, C] implements Has<A, There<Here>>. The part that's magic is, as a user of frunk, you don't typically need to worry about these indices, because the rust compiler will automatically solve for them behind the scenes, as long as they are unique.

But what about a type like Hlist![A, A, B]? This type implements both Has<A, Here> and Has<A, There<Here>>. If you try to use it, you get a type inference error unless you specify the indices:

struct Thing;

fn foo<N, List: Has<Thing, N>>() {
}

fn main() {
    foo::<Hlist![Thing, &str, f64], _>(); // okay
    foo::<Hlist![&str, Thing, f64], _>(); // okay
    foo::<Hlist![Thing, Thing, f64], _>(); // error[E0282]: type annotations needed

    // this works, but index types can easily get out of hand if you have
    // to write them manually...
    foo::<Hlist![Thing, Thing, f64], Here>();
}

Generally speaking, I expect that no matter how you try to write this Hlist![A, B] + Hlist![A, C] == Hlist![A, B, C] function, you will end up running into a type inference error like the above.

[ExpHP]

Now, about the XY problem concern.... yes, I think there could be another way to address your needs. Because you can't really build up a full list of dependencies from the list of dependents, you'll need to draw them down instead. I.e., let the caller define the input type, and require that it is able to provide the things you need.

The first step towards this is that I might suggest parameterizing the trait over the context:

trait SomeTrait<Ctx, Idxs> {
    fn do_something(ctx: Ctx);
}

impl<Idxs1, Ctx> SomeTrait<Ctx, Idxs1> for A
where
  Ctx: Sculptor<Hlist![u8], Idxs1>
{ ... }

impl<Idxs1, Idxs2, Ctx, T> SomeTrait<Ctx, (Idxs1, Idxs2)> Parent<T>
where
  Ctx: Sculptor<Hlist![u8, String], Idxs1> + Clone,
  T: SomeTrait<Ctx, Idxs2>,
{ ... }

Something like that, possibly?

[kitlith]

The first step towards this is that I might suggest parameterizing the trait over the context:

yeah, that's what i was referring to by "I know this is possible if I make SomeTrait generic on Ctx instead of making it an associated type" though at that point i'd be using Selector directly instead, probably.

let's consider a closely related but simpler example: Suppose that we wish to define a trait Has<A> which is implemented by any HList that contains at least one A.

Funny that you should mention this, I actually managed to get this to work on nightly using the unstable #[marker] attribute for traits. This was before I discovered frunk, and hlists in general, and I wrote https://github.com/kitlith/typemap_core (which of course i don't reccomend using at this point if anyone comes down into the issues and reads this).

Of course, I doubt the same approach would work for the merging behaviour I was looking into. But it was worth asking given the indexing workaround you guys are more familiar with than I am.

Thanks!