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 repo
// 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>:
// 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
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
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:
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 syntax, and attaching associated traits to each "typeclass":
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:
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.