How to reverse a `Coproduct::subset()` after mapping both halves?

[BGR360]

I have an interesting challenge:

I need to map some coproduct type Coprod!(A, B, C, D) to Coprod!(T, U, V, W). However, I have to be able to perform this mapping in two arbitrarily-partitioned steps.

So I need to be able to, say, break the input into (A, B) and (C, D), then map them to (T, U) and (V, W) separately, then embed one of those into (T, U, V, W).

So basically this:

pub fn challenge<
    Input,
    Output,
    Subset,
    SubsetMapper,
    SubsetMapperOutput,
    RemainderMapper,
    RemainderMapperOutput,
    I,
    J,
    K,
>(
    input: Input,
    subset_mapper: SubsetMapper,
    remainder_mapper: RemainderMapper,
) -> Output
where
    Input: CoproductSubsetter<Subset, I>,

    Subset: CoproductMappable<SubsetMapper, Output = SubsetMapperOutput>,
    SubsetMapperOutput: CoproductEmbedder<Output, J>,

    Input::Remainder: CoproductMappable<RemainderMapper, Output = RemainderMapperOutput>,
    RemainderMapperOutput: CoproductEmbedder<Output, K>,
{
    match input.subset() {
        Ok(subset) => {
            let subset_output = subset.map(subset_mapper);
            subset_output.embed()
        }
        Err(remainder) => {
            let remainder_output = remainder.map(remainder_mapper);
            remainder_output.embed()
        }
    }
}

Why

This is for the effect system I'm working on. When an effectful computation a calls another effectful computation b, it has the option to intercept any subset of the effects that b raises and re-raise the rest to the caller. So in some made-up language:

effect A -> T;
effect B -> U;
effect C -> V;
effect D -> W;

fn b() raises A | B | C | D {
    let t = raise A;
    let u = raise B;
    let v = raise C;
    let w = raise D;
}

fn a() raises C | D {
    try {
        b()
    } with {
        A => resume T,
        B => resume U,
    } /* implicitly re-raises C and D to be handled by the caller */
}

In Rust the effectful computations are implemented as generators where each raised effect does a yield of a Coprod!(<the effects>) and awaits a message of Coprod!(<the effect outputs>):

// `let t = raise A;`
let t: T = {
    let (send, recv) = channel();
    yield (Coprod!(A, B, C, D)::inject(A), send);
    let resolved: Coprod!(T, U, V, W) = recv.recv();
    resolved.uninject().unwrap()
}

This actually works for the example I gave. This compiles just fine:

struct A;
struct B;
struct C;
struct D;

struct T;
struct U;
struct V;
struct W;

type Input = Coprod!(A, B, C, D);
type Output = Coprod!(T, U, V, W);

type Subset = Coprod!(A, B);

let subset_mapper = hlist![|A| T, |B| U];
let remainder_mapper = hlist![|C| V, |D| W];

let output: Output = challenge::<_, _, Subset, _, _, _, _, _, _, _>(
    Input::inject(A),
    subset_mapper,
    remainder_mapper,
);
assert!(output.get::<T, _>().is_some());

The real challenge is that T, U, V, W are not guaranteed to be unique types. If I make the following changes:

type Output = Coprod!(T, U, T, U);

let remainder_mapper = hlist![|C| T, |D| U];

Then it fails to perform inference on the J and K indices due to multiple applicable impls:

error[E0283]: type annotations needed
   --> src/private.rs:262:26
    |
262 |     let output: Output = challenge::<_, _, Subset, _, _, _, _, _, _, _>(
    |                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot infer type of the type parameter `J` declared on the function `challenge`
    |

So it seems I have to somehow remember the indices from the subset operation. This wouldn't be so hard if all I need to do is re-embed the Ok() half. I think I could make some wrapper type that remembers the indices I of the original subset() call and uses those to embed the partial output into the final output.

But the tricky bit is that I also need to be able to re-embed the remainder half into the output type.

I've been staring at the CoproductSubsetter code on my screen for a couple of hours now and can't figure out how one might go about doing this. Is it possible to somehow get the "inverse" of the indices inferred for the subset() call?

[lloydmeta]

This is indeed looking like it would be tough, esp the multiple applicable impls part.

I wonder: would it help your usecase if (and I have yet to really think this through if it's feasible) there was a way to "dedupe" the types in a Coprod, just to get rid of the multiple impls issue (e.g. Coprod!(T, U, T, V) becomes Coprod!(T, U, V)) ?

[BGR360]

Hm yeah I think that would be acceptable. All that matters is that the effectful computation is able to uninject a T, U, or V after the effect is handled.

EDIT: Although, that would throw a bit of a wrench into how I'm implementing Effect on these types:

/// Marks types that are raised from effectful computations.
pub trait Effect {
    /// The type that is returned back to the effectful computation by the effect handler(s).
    type Output;
}

impl Effect for CNil {
    type Output = CNil;
}

impl<Head, Tail> Effect for Coproduct<Head, Tail>
where
    Head: Effect,
    Tail: Effect,
{
    type Output = Coproduct<Head::Output, Tail::Output>;
}

^ That is precisely why I have this problem in the first place (where (A, B, C, D) can map to (T, U, T, U)).

I have two other ideas brewing:

1. Reify the indices that come out of subset() and use them for the embedding:

fn reified_subset<Super, Sub, Indices, RemainderIndices>(
    sup: Super
) -> (Result<Sub, Super::Remainder>, Indices, RemainderIndices)
where
    Super: CoproductSubsetter<Sub, Indices>,
    Super::Remainder: CoproductEmbedder<Super, RemainderIndices>,
    Indices: Default,
    RemainderIndices: Default,
{
    (sup.subset(), Indices::default(), RemainderIndices::default())
}

I think this should work because I know that the indices needed to embed the mapped subset/remainder into the final output are the same as the indices that were needed to take the subset in the first place.

2. Add a second associated type to CoproductSubsetter which is the RemainderIndices (or make an extension trait like IndexedCoproductSubsetter that has that). I think if you have a way of knowing the full HList of indices for a Coproduct, then you can build up the RemainderIndices by somehow "subtracting" from that set in the trait impls. But I'm still not too well-versed in how these indices are built up.

[BGR360]

Oh, hmmm, I thought this would work but it doesn't:

use frunk::coproduct::{CoproductEmbedder, CoproductMappable, CoproductSubsetter};
use frunk::{hlist, Coprod};

pub fn challenge<
    Input,
    Output,
    Subset,
    SubsetMapper,
    SubsetMapperOutput,
    RemainderMapper,
    RemainderMapperOutput,
    Indices,
    RemainderIndices,
>(
    input: Input,
    subset_mapper: SubsetMapper,
    remainder_mapper: RemainderMapper,
) -> Output
where
    Input: CoproductSubsetter<Subset, Indices>,
    Input::Remainder: CoproductEmbedder<Input, RemainderIndices>,  // <--------

    Subset: CoproductMappable<SubsetMapper, Output = SubsetMapperOutput>,
    SubsetMapperOutput: CoproductEmbedder<Output, Indices>,

    Input::Remainder: CoproductMappable<RemainderMapper, Output = RemainderMapperOutput>,
    RemainderMapperOutput: CoproductEmbedder<Output, RemainderIndices>,  // <--------
{
    match input.subset() {
        Ok(subset) => {
            let subset_output = subset.map(subset_mapper);
            subset_output.embed()
        }
        Err(remainder) => {
            let remainder_output = remainder.map(remainder_mapper);
            remainder_output.embed()
        }
    }
}

Usage

struct A;
struct B;
struct C;
struct D;

struct T;
struct U;
struct V;
struct W;

fn easy_mode() {
    type Input = Coprod!(A, B, C, D);
    type Output = Coprod!(T, U, V, W);

    type Subset = Coprod!(A, B);

    let subset_mapper = hlist![|A| T, |B| U];
    let remainder_mapper = hlist![|C| V, |D| W];

    let output: Output = challenge::<_, _, Subset, _, _, _, _, _, _>(
        Input::inject(A),
        subset_mapper,
        remainder_mapper,
    );
    assert!(output.get::<T, _>().is_some());
}

fn hard_mode() {
    type Input = Coprod!(A, B, C, D);
    type Output = Coprod!(T, U, T, U);

    type Subset = Coprod!(A, B);

    let subset_mapper = hlist![|A| T, |B| U];
    let remainder_mapper = hlist![|C| T, |D| U];

    let output: Output = challenge::<_, _, Subset, _, _, _, _, _, _>(
        Input::inject(A),
        subset_mapper,
        remainder_mapper,
    );
    assert!(output.get::<T, _>().is_some());
}

Error

error[E0277]: the trait bound `Coproduct<T, Coproduct<U, Coproduct<V, Coproduct<W, CNil>>>>: CoprodInjector<U, Here>` is not satisfied
  --> examples/challenge.rs:60:26
   |
60 |     let output: Output = challenge::<_, _, Subset, _, _, _, _, _, _>(
   |                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `CoprodInjector<U, Here>` is not implemented for `Coproduct<T, Coproduct<U, Coproduct<V, Coproduct<W, CNil>>>>`
   |
   = help: the following other types implement trait `CoprodInjector<InjectType, Index>`:
             <Coproduct<Head, Tail> as CoprodInjector<I, There<TailIndex>>>
             <Coproduct<I, Tail> as CoprodInjector<I, Here>>
   = note: required because of the requirements on the impl of `CoproductEmbedder<Coproduct<T, Coproduct<U, Coproduct<V, Coproduct<W, CNil>>>>, HCons<Here, HNil>>` for `Coproduct<U, CNil>`
   = note: 1 redundant requirement hidden
   = note: required because of the requirements on the impl of `CoproductEmbedder<Coproduct<T, Coproduct<U, Coproduct<V, Coproduct<W, CNil>>>>, HCons<Here, HCons<Here, HNil>>>` for `Coproduct<T, Coproduct<U, CNil>>`
note: required by a bound in `challenge`
  --> examples/challenge.rs:24:25
   |
4  | pub fn challenge<
   |        --------- required by a bound in this
...
24 |     SubsetMapperOutput: CoproductEmbedder<Output, Indices>,
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `challenge`

error[E0277]: the trait bound `Coproduct<T, Coproduct<U, Coproduct<T, Coproduct<U, CNil>>>>: CoprodInjector<U, Here>` is not satisfied
  --> examples/challenge.rs:77:26
   |
77 |     let output: Output = challenge::<_, _, Subset, _, _, _, _, _, _>(
   |                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `CoprodInjector<U, Here>` is not implemented for `Coproduct<T, Coproduct<U, Coproduct<T, Coproduct<U, CNil>>>>`
   |
   = help: the following other types implement trait `CoprodInjector<InjectType, Index>`:
             <Coproduct<Head, Tail> as CoprodInjector<I, There<TailIndex>>>
             <Coproduct<I, Tail> as CoprodInjector<I, Here>>
   = note: required because of the requirements on the impl of `CoproductEmbedder<Coproduct<T, Coproduct<U, Coproduct<T, Coproduct<U, CNil>>>>, HCons<Here, HNil>>` for `Coproduct<U, CNil>`
   = note: 1 redundant requirement hidden
   = note: required because of the requirements on the impl of `CoproductEmbedder<Coproduct<T, Coproduct<U, Coproduct<T, Coproduct<U, CNil>>>>, HCons<Here, HCons<Here, HNil>>>` for `Coproduct<T, Coproduct<U, CNil>>`
note: required by a bound in `challenge`
  --> examples/challenge.rs:24:25
   |
4  | pub fn challenge<
   |        --------- required by a bound in this
...
24 |     SubsetMapperOutput: CoproductEmbedder<Output, Indices>,
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `challenge`

I assume this is because CoproductSubsetter and CoproductEmbedder have different ways of expressing the indices? I guess for this to work you'd need a way to convert Subsetter indices into Embedder indices.

[BGR360]

Oh wait! I just needed one more piece!

pub fn challenge<
    Input,
    Output,
    Subset,
    SubsetMapper,
    SubsetMapperOutput,
    RemainderMapper,
    RemainderMapperOutput,
    Indices,
    SubsetIndices, // <--------
    RemainderIndices,
>(
    input: Input,
    subset_mapper: SubsetMapper,
    remainder_mapper: RemainderMapper,
) -> Output
where
    Input: CoproductSubsetter<Subset, Indices>,

    Subset: CoproductEmbedder<Input, SubsetIndices>, // <--------
    Input::Remainder: CoproductEmbedder<Input, RemainderIndices>,

    Subset: CoproductMappable<SubsetMapper, Output = SubsetMapperOutput>,
    SubsetMapperOutput: CoproductEmbedder<Output, SubsetIndices>, // <--------

    Input::Remainder: CoproductMappable<RemainderMapper, Output = RemainderMapperOutput>,
    RemainderMapperOutput: CoproductEmbedder<Output, RemainderIndices>,
{
    match input.subset() {
        Ok(subset) => {
            let subset_output = subset.map(subset_mapper);
            subset_output.embed()
        }
        Err(remainder) => {
            let remainder_output = remainder.map(remainder_mapper);
            remainder_output.embed()
        }
    }
}

That one works!