# How to implement a type-level map with an identity function?

**URL:** <https://users.rust-lang.org/t/how-to-implement-a-type-level-map-with-an-identity-function/119745>\
**Category:** help\
**Created:** [October 14, 2024, 11:39pm UTC](https://users.rust-lang.org/t/how-to-implement-a-type-level-map-with-an-identity-function/119745 "2024-10-14T23:39:27Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![joshlf](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/joshlf/32/3412_2.png) [@joshlf](https://users.rust-lang.org/u/joshlf)\
**Post date:** [October 14, 2024, 11:39pm UTC](https://users.rust-lang.org/t/how-to-implement-a-type-level-map-with-an-identity-function/119745/1 "2024-10-14T23:39:27Z")

</div>

I'm working on a type-level map over a set of types. It looks like this:

```rust
trait Trait {
    type MappedTo<M: Mapping>: Trait;
}

trait Mapping {
    type FromA: Trait;
    type FromB: Trait;
}

enum Identity {}

impl Mapping for Identity {
    type FromA = A;
    type FromB = B;
}

enum A {}
impl Trait for A {
    type MappedTo<M: Mapping> = M::FromA;
}

enum B {}
impl Trait for B {
    type MappedTo<M: Mapping> = M::FromB;
}

#[allow(type_alias_bounds)]
type Mapped<T: Trait, M: Mapping> = T::MappedTo<M>;

```

The idea is that `Mapped<T, M>` applies the mapping `M` to the type `T`. We need to know that this mapping is applicable for all `T: Trait`, and so we put the actual mapping machinery _in_ `Trait` itself (the associated `MappedTo` type).

This works, but it has a usability problem: In a context in which `T: Trait` is generic and `Identity` is concrete, the type system isn't smart enough to know that `Mapped<T, Identity> = T`.

I tried to solve that by adding the following bound to `Trait`:

```rust
// Polyfill for type equality in where bounds
trait Equal<T: ?Sized> {}
impl<T: ?Sized> Equal<T> for T {}

trait Trait
where
    <Self as Trait>::MappedTo<Identity>: Equal<Self>
{
    ...
}

```

That made the associated type itself choke:

```plaintext
error[E0277]: the trait bound `<<Self as Trait>::MappedTo<M> as Trait>::MappedTo<Identity>: Equal<<Self as Trait>::MappedTo<M>>` is not satisfied
  --> src/lib.rs:10:32
   |
10 | type MappedTo<M: Mapping>: Trait;
   | ^^^^^ the trait `Equal<<Self as Trait>::MappedTo<M>>` is not implemented for `<<Self as Trait>::MappedTo<M> as Trait>::MappedTo<Identity>`
   |
note: required by a bound in `Trait`
  --> src/lib.rs:8:42
   |
6 | trait Trait
   | ----- required by a bound in this trait
7 | where
8 | <Self as Trait>::MappedTo<Identity>: Equal<Self>
   | ^^^^^^^^^^^ required by this bound in `Trait`
help: consider further restricting the associated type
   |
8 | <Self as Trait>::MappedTo<Identity>: Equal<Self>, <<Self as Trait>::MappedTo<M> as Trait>::MappedTo<Identity>: Equal<<Self as Trait>::MappedTo<M>>
   | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

```

What if we move the `where` bound to `type MappedTo`?

```rust
trait Trait {
    type MappedTo<M: Mapping>: Trait
    where
        <Self as Trait>::MappedTo<Identity>: Equal<Self>;
}

```

This causes an overflow when evaluating the `where` bound requirement on the impls themselves:

```plaintext
error[E0275]: overflow evaluating the requirement `<A as Trait>::MappedTo<Identity> == _`
  --> src/lib.rs:26:5
   |
26 | type MappedTo<M: Mapping> = M::FromA;
   | ^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0275]: overflow evaluating the requirement `<B as Trait>::MappedTo<Identity> == _`
  --> src/lib.rs:31:5
   |
31 | type MappedTo<M: Mapping> = M::FromB;
   | ^^^^^^^^^^^^^^^^^^^^^^^^^

```

I've tried a few other things, similarly to no success. Any ideas on how I can get this to work?

---

<div class="post-metadata">

**Author:** ![quinedot](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/quinedot/32/17693_2.png) [@quinedot](https://users.rust-lang.org/u/quinedot)\
**Post date:** [October 14, 2024, 11:58pm UTC](https://users.rust-lang.org/t/how-to-implement-a-type-level-map-with-an-identity-function/119745/2 "2024-10-14T23:58:47Z")

</div>

Does this work for you?

```rust
trait Trait: BaseTrait<MappedTo<Identity> = Self> {}

impl<T: ?Sized + BaseTrait> Trait for T
where 
    T: BaseTrait<MappedTo<Identity> = T>
{}

trait BaseTrait {
    type MappedTo<M: Mapping>: Trait;
}

impl BaseTrait for A {
    type MappedTo<M: Mapping> = M::FromA;
}

impl BaseTrait for B {
    type MappedTo<M: Mapping> = M::FromB;
}

// the rest unchanged

trait Mapping {
    type FromA: Trait;
    type FromB: Trait;
}

enum Identity {}

impl Mapping for Identity {
    type FromA = A;
    type FromB = B;
}

enum A {}
enum B {}

#[allow(type_alias_bounds)]
type Mapped<T: Trait, M: Mapping> = T::MappedTo<M>;

```

---

<div class="post-metadata">

**Author:** ![joshlf](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/joshlf/32/3412_2.png) [@joshlf](https://users.rust-lang.org/u/joshlf)\
**Post date:** [October 15, 2024, 12:06am UTC](https://users.rust-lang.org/t/how-to-implement-a-type-level-map-with-an-identity-function/119745/3 "2024-10-15T00:06:41Z")

</div>

Wooo that works! Thank you so much! Had been banging my head on that one for hours...

---

<div class="post-metadata">

**Author:** ![system](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/system/32/51372_2.png) [@system](https://users.rust-lang.org/u/system)\
**Post date:** [January 13, 2025, 12:06am UTC](https://users.rust-lang.org/t/how-to-implement-a-type-level-map-with-an-identity-function/119745/4 "2025-01-13T00:06:47Z")

</div>

Closed on January 13, 2025, 12:06am UTC

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.