# Restricting GAT type-parameter struggle

**URL:** <https://users.rust-lang.org/t/restricting-gat-type-parameter-struggle/126109>\
**Category:** help\
**Created:** [February 23, 2025, 5:22pm UTC](https://users.rust-lang.org/t/restricting-gat-type-parameter-struggle/126109 "2025-02-23T17:22:36Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![AndreiCravtov](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/andreicravtov/32/45700_2.png) [@AndreiCravtov](https://users.rust-lang.org/u/AndreiCravtov)\
**Post date:** [February 23, 2025, 5:22pm UTC](https://users.rust-lang.org/t/restricting-gat-type-parameter-struggle/126109/1 "2025-02-23T17:22:36Z")

</div>

I've seen many approaches to encode HKTs in Rust using GATs:

1 - Type Families approach, this one is for example a modified version of the code from [mschuwalow/ratz](https://github.com/mschuwalow/ratz/blob/main/src/hkt.rs) repo

```rust
// type-constructor abstraction
trait TyCon { type K<A>: Constructed<TyCon = Self, A = A>; }

trait AppliedTyCon<A>: TyCon { type Constructed: Constructed<TyCon = Self, A = A>; }
impl<F: TyCon, A> AppliedTyCon<A> for F { type Constructed = Self::K<A>; }

trait Constructed { type A; type TyCon: AppliedTyCon<Self::A, Constructed = Self>; }

// typeclass traits
trait Functor: TyCon { 
  fn map<A, B, F: Fn(A) -> B>(fa: Self::K<A>, f: F) -> Self::K<B>;
}
trait Applicative: Functor {
  fn pure<A>(a: A) -> Self::K<A>;
  fn ap<A, B, F: Fn(A) -> B>(ff: Self::K<F>, fa: Self::K<A>) -> Self::K<B>;
}
...

```

That is all fine and good, and I can even implement the whole thing for simple types like `Option<A>` etc., but then I get to `Vec<A>`:

```rust
// type-constructor abstraction
struct VecFamily;
impl TyCon for VecFamily { type K<A> = Vec<A>; }
impl<A> Constructed for Vec<A> { type A = A; type TyCon = VecFamily; }

impl Functor for VecFamily {
  fn map<A, B, F: Fn(A) -> B>(fa: Vec<A>, f: F) -> Vec<B> {
    fa.into_iter().map(f).collect()
  }
}
impl Applicative for VecFamily {
  fn pure<A>(a: A) -> Vec<A> { vec![a] }
  fn ap<A, B, F: Fn(A) -> B>(ff: Vec<F>, fa: Vec<A>) -> Vec<B> {
    // unimplementable...... requires `A: Clone`
  }
}

```

And this is where I run into a dead end. In order for `Vec<A>` to implement `ap` correctly, it has to essentially produce a Cartesian product like this:  
`ap([f(_), g(_), h(_)], [a, b, c]) => [f(a), f(b), f(c), g(a), g(b), g(c), h(a), h(b), h(c)]`  
And for that, I need `A: Clone`, meaning that I can only define an `Applicative` instance on the subset of `Vec<A> where A: Clone`, and I have _ **no** _ idea how to express that within the type-system. The issue is, the `TyCon` trait _ **forces** _ the `A` in `Self::K<A>` to _ **not** _ have any additional bounds (besides implicit `Sized`) so the issue boils down to: how can I restrict the generic of a GAT in some way?

2 - Type-equality + Plug/Unplug approach without type families:  
Use a helper trait for type equality constraints

```rust
trait TyEq { type Rhs: TyEq<Rhs = Self> + ?Sized; }  
impl<T> TyEq for T { type Rhs = T; }

```

And then a modified version of the code from [this answer](https://langdev.stackexchange.com/a/3224)

```rust
trait HKT: TyEq<Rhs = Self::Unplug<Self::Plug>> {
  type Plug;  
  type Unplug<B>: HKT<Plug = B>;  
}  
trait Functor: HKT {  
  type FunctorUnplug<B>: TyEq<Rhs = Self::Unplug<B>> + Functor<Plug = B>;  
  fn map<F: Fn(Self::Plug) -> B, B>(self, f: F) -> Self::FunctorUnplug<B>;  
}  
trait Applicative: Functor {  
  type ApplicativeUnplug<B>: TyEq<Rhs = Self::Unplug<B>> + Applicative<Plug = B>;  
  fn pure(a: Self::Plug) -> Self;  
  fn ap<B, F: Fn(Self::Plug) -> B>(self, ff: Self::Unplug<F>) -> Self::ApplicativeUnplug<B>;  
}
...

```

Where the additional GATs `FunctorUnplug` and `ApplicativeUnplug` propagate type information, so the returned values are treated as `Functor/Applicative` rather than just `HKT`. And again, when implementing `Applicative` for `Vec<A>` I run into the issue of needing `Vec<A> where A: Clone`:

```rust
impl<A> HKT for Vec<A> { type Plug = A; type Unplug<B> = Vec<B>; }
impl<A> Functor for Vec<A> {
  type FunctorUnplug<B> = Vec<B>;
  fn map<F: Fn(A) -> B, B>(self, f: F) -> Vec<B> {
    self.into_iter().map(f).collect()  
  }  
}  
impl<A: Clone> Applicative for Vec<A> {
  type ApplicativeUnplug<B> = Vec<B>; // ERROR: requies `B: Clone`
  fn pure(a: A) -> Vec<A> { vec![a] }  
  fn ap<B, F: Fn(A) -> B>(self, ff: Vec<F>) -> Vec<B> {  
	ff.into_iter()  
	  .flat_map(|f| self.clone().into_iter().map(f))  
	  .collect()
  }
}

```

So its once again an issue of restricting the input of a GAT.

And there are probably all sorts of other GAT encodings of HKTs, but they will all probably run into the issue of restricting the the GAT input at some point and how exactly to express it. I've tried to figure something out for weeks and I can't seem to write down a way to express this.

The closest I got (at least with the plug/unplug approach) was using hypothetical [associated/generic trait](https://github.com/rust-lang/rfcs/issues/2190) syntax, and attaching associated traits to each "typeclass":

```rust
trait TyEq { type Rhs: TyEq<Rhs = Self> + ?Sized; }  
impl<T> TyEq for T { type Rhs = T; }  

trait All {}  
impl<T: ?Sized> All for T {}  
  
trait HKT: TyEq<Rhs = Self::Unplug<Self::Plug>> {
  trait Bound;  
  type Plug;  
  type Unplug<B: Self::Bound>: HKT<Plug = B>;  
}  
trait Functor: HKT {  
  trait FunctorBound;  
  type FunctorUnplug<B>: TyEq<Rhs = Self::Unplug<B>> + Functor<Plug = B>   
    where B: Self::Bound + Self::FunctorBound;  
  fn map<F: Fn(Self::Plug) -> B, B>(self, f: F) -> Self::FunctorUnplug<B>  
    where B: Self::Bound + Self::FunctorBound;  
}  
trait Applicative: Functor {  
  trait ApplicativeBound;  
  type ApplicativeUnplug<B>: TyEq<Rhs = Self::Unplug<B>> + Applicative<Plug = B>  
    where B: Self::Bound + Self::ApplicativeBound;  
  fn pure(a: Self::Plug) -> Self;  
  fn ap<B, F: Fn(Self::Plug) -> B>(self, ff: Self::Unplug<F>) -> Self::ApplicativeUnplug<B>  
    where B: Self::Bound + Self::ApplicativeBound;  
}

```

Which finally lets me express that `Vec<A> where A: Clone` is an `Applicative`:

```rust
impl<A> HKT for Vec<A> {  
  trait Bound = All;  
  type Plug = A;  
  type Unplug<B: All> = Vec<B>;  
}  
impl<A> Functor for Vec<A> {  
  trait FunctorBound = All;  
  type FunctorUnplug<B: All> = Vec<B>;  
  fn map<F: Fn(A) -> B, B: All>(self, f: F) -> Vec<B> {  
    self.into_iter().map(f).collect()  
  }  
}  
impl<A: Clone> Applicative for Vec<A> {  
  trait ApplicativeBound = Clone;  
  type ApplicativeUnplug<B: All + Clone> = Vec<B>; // No more errors here
  
  fn pure(a: A) -> Vec<A> { vec![a] }  
  fn ap<B: All + Clone, F: Fn(A) -> B>(self, ff: Vec<F>) -> Vec<B> {  
    ff.into_iter()  
      .flat_map(|f| self.clone().into_iter().map(f))  
      .collect()  
  }
}

```

However, this associated-trait business isn't even an approved proposal, so its this "solution" is nothing except wishful thinking.

So the question is, is there some kind of really hacky workaround, or maybe some combination of unstable features, which would let me emulate these restrictions on the GAT input parameter? Or express `Vec<A> where A: Clone` is an `Applicative` in some way, shape, or form? So far I couldn't come up with anything.

---

<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:** [May 24, 2025, 5:22pm UTC](https://users.rust-lang.org/t/restricting-gat-type-parameter-struggle/126109/2 "2025-05-24T17:22:36Z")

</div>

Closed on May 24, 2025, 5:22pm 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.