Rust already has a way to represent Functor using Generic Associated Types (GATs):
pub trait Functor<A> {
type With<B>: Functor<B>;
fn map<B>(self, f: impl Fn(A) -> B) -> Self::With<B>;
}
In this trait, Self is the functor type specialized to A, and With<B> is the functor type specialized to B (With<B> is how we emulate "higher-kinded types"). For example:
/// Dummy functor-able type
pub struct Foonctor<A>(Vec<A>, A);
impl<A> Functor<A> for Foonctor<A> {
type With<B> = Foonctor<B>;
fn map<B>(self, f: impl Fn(A) -> B) -> Self::With<B> {
Foonctor(self.0.into_iter().map(&f).collect(), f(self.1))
}
}
(playground link)
Interestingly enough, using only 2 tiny modifications, we can already make any Iterator implement Functor via blanket impl. The first modification is to add the map function's type to With, making it With<F, B>; the second modification is to make With<B> not the same type as Self but with a different parameter, but instead make it std::iter::Map<Self, F>:
/// New functor trait
pub trait Functor<A> {
type With<F: Fn(A) -> B, B> = Functor<B>;
fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B>;
}
/// We can still implement the new trait wherever we could implement the old one
impl<A> Functor<A> for Foonctor<A> {
type With<F: Fn(A) -> B, B> = Foonctor<B>;
fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B> {
// Same exact implementation as before
Foonctor(Iterator::map(self.0.into_iter(), &f).collect(), f(self.1))
}
}
/// But now we can also implement it for arbitrary iterators, using std::iter::Map
impl<A, I: Iterator<Item=A>> Functor<A> for I {
type With<F: Fn(A) -> B, B> = std::iter::Map<I, F>;
fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B> {
Iterator::map(self, f)
}
}
(playground link)
However, there's one problem with the above: the functor impl for the iterator trait is a blanket impl, which prevents impls for other traits. There's a good reason for this: if Functor was blanket implemented for 2 traits, what implementation would an object which implements both traits choose? So until the specialization RFC gets accepted, this solution is non-ideal.
What we can do, though, is instead of implementing on the trait directly, use the newtype pattern and implement it on the newtype. Then you can use newtypes for other traits as well (this sidesteps the ambiguity problem because even if an object implements multiple traits, you can only choose one newtype to wrap it with and must choose one explicitly)*:
/// Trait newtype
pub struct IteratorFunctor<A, I: Iterator<Item=A>>(I);
/// Another trait newtype
pub struct FutureFunctor<A, Fut: futures::Future<Output=A>>(Fut);
/// Emulate implementing functor for a trait, by implementing on its newtype
impl<A, I: Iterator<Item=A>> Functor<A> for IteratorFunctor<A, I> {
/// Note that we also have to wrap the `With` type with the newtype
type With<F: Fn(A) -> B, B> = IteratorFunctor<B, std::iter::Map<I, F>>;
fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B> {
IteratorFunctor(self.0.map(f))
}
}
/// Emulate implementing functor for another trait
impl<A, Fut: futures::Future<Output=A>> Functor<A> for FutureFunctor<A, Fut> {
type With<F: Fn(A) -> B, B> = FutureFunctor<B, futures::future::Map<Fut, F>>;
fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B> {
use futures::future::FutureExt;
FutureFunctor(self.0.map(f))
}
}
/// Demo
fn main() {
// Iterator example: [1, 2, ... 10]
let elems = 1..=10;
// map (* 2) elems
let mapped_elems = IteratorFunctor(elems).map(|e| e * 2).0;
// [2, 4, ... 20]
println!("{:?}", mapped_elems.collect::<Vec<_>>());
// Future example: { <complex calculation> = "complex calculated value" }
let future = async {
// Pretend we're douing some complex calculation with `.await`s here
"complex calculated value"
};
// map length future
let mapped_future = FutureFunctor(future).map(|f| f.len()).0;
// { <complex calculation |> length> = 24 }
println!("{:?}", futures::executor::block_on(mapped_future));
}
Here's the complete finished code (playground link)
* (In our specific example, this also makes it easier to demo actually using the trait, because Iterator::map is already defined. If we demo'd the second-last example, we'd have to explicitly call Functor::map, like how we explicitly called Iterator::map in the Foonctor impl. This isn't an issue for every blanket impl in general, it just so happens to be here, because Functor isn't the only in-scope trait which defines a method named map)
Also, for why this works even though Rust trait implementations can be different sizes: the size of std::iter::Map<I, F> is the size of whatever I it's given plus the size of F. If we call Functor::map twice we'll get IteratorFunctor<C, Map<Map<I, F0>, F1>>, 3 times and we'll get IteratorFunctor<D, Map<Map<Map<I, F0>, F1>, F2>>, etc.; all these types have different sizes, but they're all represented at compile-time and their sizes are known at compile-time.
If you're doing something where the compiler doesn't know how many times map will be called at compile time (e.g. call map in a loop): you can convert any iterator into a Box<dyn Iterator<Item=A>>, slightly modify Functor again (add a lifetime to With which bounds F), and add another newtype wrapper which returns the same type given the same type parameter:
pub trait Functor<A> {
/// New modification: we have to add a lifetime parameter and bound `F` by it
type With<'b, F: Fn(A) -> B + 'b, B>: Functor<B> where Self: 'b;
fn map<'b, F: Fn(A) -> B + 'b, B>(self, f: F) -> Self::With<'b, F, B> where Self: 'b;
}
/// This wrapper doesn't contain the iterator, so we can erase the `std::iter::Map` wrappers.
/// The underlying iterator is allocated on the heap so we don't need to know its size
/// (i.e. how many times `map` was called) at compile-time
pub struct BoxIteratorFunctor<'a, A>(Box<dyn Iterator<Item=A> + 'a>);
impl<'a, A> Functor<A> for BoxIteratorFunctor<'a, A> {
/// No `std::iter::Map` or `F` in the result type
type With<'b, F: Fn(A) -> B + 'b, B> = BoxIteratorFunctor<'b, B> where Self: 'b;
fn map<'b, F: Fn(A) -> B + 'b, B>(self, f: F) -> Self::With<'b, F, B> where Self: 'b {
BoxIteratorFunctor(Box::new(self.0.map(f)))
}
}
/// Demo
fn main() {
// Iterator example: [1, 2, ... 10]
let mut elems = BoxIteratorFunctor(Box::new(1u64..=10));
for _ in 1..5 {
// map (^ 2) elems
// We can assign to the same variable, because it's the same type:
// `BoxIteratorFunctor<'static, u64>`
elems = elems.map(move |e| e * e);
}
// [((((1^2)^2)^2)^2)^2, ((((2^2)^2)^2)^2)^2 ... ((((10^2)^2)^2)^2)^2]
println!("{:?}", elems.0.collect::<Vec<_>>());
}
(playground)
