How can I implement a Functor trait in Rust?

Question

I'm working through Category Theory for Programmers and one of its challenges is to implement a Functor interface.

This question provides the following solution:

pub trait Functor<A> {
    type With<B>: Functor<B>;
    fn map<B>(self, f: impl Fn(A) -> B) -> Self::With<B>;
}

However, this would allow With to be any type that implements functor. What I really want would be something like this:

pub trait Functor<A> {
    fn map<B>(self, f: impl Fn(A) -> B) -> Self<B>;
}

But Self does not accept type parameters. How can I get around this?

Answer 1

As with another problem in computer science, by adding a level of indirection. That is, you can define a family of related types, then use that to enforce the appropriate constraint.

A family is, in the end, fairly trivial:

trait Family {
    type Member<T>;
}

trait FamilyMember<T> {
    type Of: Family<Member<T> = Self>;
}

struct VecFamily;

impl Family for VecFamily {
    type Member<T> = Vec<T>;
}

impl<T> FamilyMember<T> for Vec<T> {
    type Of = VecFamily;
}

And then you can leverage that with functors:

trait Functor<A>: FamilyMember<A> {
    fn map<B>(self, f: impl FnMut(A) -> B) -> <Self::Of as Family>::Member<B>;
}

impl<A> Functor<A> for Vec<A> {
    fn map<B>(self, f: impl FnMut(A) -> B) -> Vec<B> {
        self.into_iter().map(f).collect()
    }
}

It's a bit of mouthful... but it does compile on stable!