Inspired by these posts
- Convert
Option<&str>
toOption<PathBuf>
- My latest response to "How to cache a vector’s capacity?"
From<Type<A>>
forType<B>
and reading through Monads and GATs in nightly Rust (from December 2020), I wondered if there's a way to implement functors in Rust.
Michael Snoyman writes in his post on Monads and GATs:
Logically, we know that for a
Option<A>
implementation, we'd likeWrapped
to be aOption<B>
kind of thing. But the GAT implementation does not enforce it. (By contrast, the HKT approach in Haskell does enforce this.)
So how can we enforce that a functor's map
function will always take a Wrapper<A>
and a F: FnMut(A) -> B
, and return a Wrapper<B>
(and not some other type Foo
, or std::io::Result<Wrapper<B>>
, for example)? I think it's possible to solve this with a type constructor and an IsType<T>
helper trait which is implemented for T
(and only for T
).
This is my attempt. Note that my Functor
is a type constructor, while the actual type that is constructed with the functor (e.g. Vec<i32>
) implements a trait that I named Wrapped
(i.e. what I call Wrapped
in my code is named Functor
in the cited blog post).
/// Helper module allowing to specify concrete types in bounds
pub mod type_bound {
mod sealed {
pub trait IsType<T: ?Sized> {}
impl<T: ?Sized> IsType<T> for T {}
}
/// Trait `IsType<T>` is implemented if and only if `Self` is `T`
pub trait IsType<T: ?Sized>: sealed::IsType<T> {
/// Convert from `T` to `Self` (no-op)
fn identity_from(x: T) -> Self
where
Self: Sized,
T: Sized;
/// Convert from `Self` to `T` (no-op)
fn identity_into(self) -> T
where
Self: Sized,
T: Sized;
}
impl<T: ?Sized> IsType<T> for T {
fn identity_from(x: T) -> Self
where
Self: Sized,
T: Sized,
{
x
}
fn identity_into(self) -> T
where
Self: Sized,
T: Sized,
{
self
}
}
}
pub mod functor {
use super::type_bound::IsType;
/// A type constructor that is a functor
pub trait Functor {
type Wrapped<Unwrapped>: Wrapped;
}
/// A type constructed by a functor (e.g. `Option<T>` or `Vec<T>`)
pub trait Wrapped
where
Self: Sized,
Self: IsType<
<Self::Functor as Functor>::Wrapped<Self::Unwrapped>,
>,
{
/// Functor that can be used to construct `Self`
type Functor: Functor;
/// Type passed to `<Self::Functor as Functor>::Wrapped`
/// (e.g. `i32`) to construct `Self` (e.g. `Vec<i32>`)
type Unwrapped;
/// Replaces inner type and value by applying a mapping function
fn map<B, F>(
self,
f: F,
) -> <Self::Functor as Functor>::Wrapped<B>
where
F: FnMut(Self::Unwrapped) -> B;
}
}
use self::functor::{Functor, Wrapped};
/// Some example implementations for [`Functor`] and [`Wrapped`]
pub mod functor_impls {
use super::*;
pub struct OptionFunctor;
impl Functor for OptionFunctor {
type Wrapped<Unwrapped> = Option<Unwrapped>;
}
impl<A> Wrapped for Option<A> {
type Functor = OptionFunctor;
type Unwrapped = A;
fn map<B, F>(self, f: F) -> Option<B>
where
F: FnMut(A) -> B,
{
Option::map(self, f)
}
}
pub struct VecFunctor;
impl Functor for VecFunctor {
type Wrapped<Unwrapped> = Vec<Unwrapped>;
}
impl<A> Wrapped for Vec<A> {
type Functor = VecFunctor;
type Unwrapped = A;
fn map<B, F>(self, f: F) -> Vec<B>
where
F: FnMut(A) -> B,
{
self.into_iter().map(f).collect()
}
}
}
fn convert_inner<T, B>(
wrapped: T,
) -> <T::Functor as Functor>::Wrapped<B>
where
T: Wrapped,
B: From<T::Unwrapped>,
{
wrapped.map(Into::into)
}
fn double_wrapped_i32<T>(
wrapped: T,
) -> <T::Functor as Functor>::Wrapped<i32>
where
T: Wrapped<Unwrapped = i32>,
{
wrapped.map(|x| x * 2)
}
fn main() {
let v: Vec<i32> = vec![1, 2, 3];
let w: Vec<f64> = convert_inner(v);
println!("w = {w:?}");
let d: Vec<i32> = double_wrapped_i32(vec![11, 12]);
println!("d = {d:?}");
}
Output:
w = [1.0, 2.0, 3.0]
d = [22, 24]
Happy to hear some feedback on my idea. Note that this is mostly a mental exercise and I don't see any real-world use case as of yet.
Edit: In my later versions (see posts below), I got rid of Functor
and renamed Wrapped
to Functor
.