I experimented with describing functors and monads in Rust, which resulted in the fmap crate. It's more of an experiment rather than a real plan to bring functional programming to Rust.
I did experience some difficulties and recently also made an interesting discovery:
First of all, It is sometimes tough for the compiler to figure out that two types are equal (or to allow the compiler to even have enough information to infer that two types will be equal). Consider this example that I basically had to go through in the other thread:
pub trait Functor<'a, B> {
type Inner: 'a;
type Mapped;
fn fmap<F>(self, f: F) -> Self::Mapped
where
F: 'a + Send + FnMut(Self::Inner) -> B;
}
impl<'a, A, B> Functor<'a, B> for Vec<A>
where
A: 'a,
B: 'a,
{
/* … */
}
fn double_inner_i32<'a, T>(functor: T) -> T
where
T: Functor<'a, i32, Inner = i32>,
// One possible fix:
// T: Functor<'a, i32, Inner = i32, Mapped = T>,
{
functor.fmap(|x| x * 2)
}
fn main() {
let mut vec = vec![1, 2, 3];
vec = double_inner_i32(vec);
println!("doubled vec = {:?}", vec);
}
(Playground)
While the extra Mapped = T constraint may be bearable in this case, it can become much more complex and difficult, which I will get back to.
Another thing I just recently discovered is that while in a functional programming language, we seem to have a hierarchy "Monad is an Applicative Functor is a Functor", this might not make that much sense in a non-purely-functional language such as Rust. That is because if we assume this hierarchy, we would need to be able to express the applicative functor's "apply" method in terms of the monad's "bind" method. How would this look like? The following is more or less pseudo-code (I'm still experimenting with it):
pub fn apply_using_bind<…>(
wrapped_closures: …,
wrapped_values: …,
) …
{
wrapped_closures.bind(move |inner_closure| {
wrapped_values.clone().fmap(inner_closure)
)
}
We need the clone() call because the move closure (that gets a closure as argument) may be called several times. Thus we will require an additional Clone bound on the wrapped_values.
We can observe this effect in the higher crate in the implementation of one of Applicative's supertraits here:
impl<'a, A> Apply<'a, A> for Vec<A>
where
A: 'a,
Vec<A>: Clone,
{
/* … */
}
Note the extra Clone bound on Vec<A>.
On the other hand, a Vec<A> where A: !Clone could totally be a monad, as shown in the implementation of Monad for Vec in my fmap crate, where we don't require a Vec<A>: Clone or A: Clone bound:
impl<'a, A, B> Monad<'a, B> for Vec<A>
where
A: 'a,
B: 'a,
{
fn bind<F>(self, mut f: F) -> Self::Mapped
where
F: 'a + Send + FnMut(/* … */) -> /* … */,
{
let mut vec = Vec::new();
for item in self.into_iter() {
for item in f(item).into_iter() {
vec.push(item);
}
}
vec
}
}
This anomaly doesn't exist in a functional language like Haskell, because it's possible to copy/clone etc. every value.
Side note: The higher crate introduces a Bind trait (as alternative to Monad, which requires Applicative).
My conclusion is that when we deal with mutation, the hierarchy of typeclasses/traits will look differently (unless I made a mistake in my reasoning). In particular: not every monad seems to be an applicative functor (but a non-applicative functor) if we do allow that all values can be cloned/copied. Not sure if there are more implications following from this.
But the bigger issue seem to be that Rust's type system currently makes reasoning about types hard and can force you to add more and more trait bounds that are difficult to comprehend (see fmap::NestedMonad for an example):
pub trait NestedMonad<'a>
where
Self: Monad<'a, <Self::InnerMonad as FunctorSelf<'a>>::Inner>,
Self: FunctorSelf<'a>,
Self: Functor<
'a,
<Self::InnerMonad as FunctorSelf<'a>>::Inner,
FmapIn = Self::Inner,
Mapped = Self::Inner,
>,
{
/// Helper type always equal to [`Self::Inner`]
///
/// This type is needed to circumvent
/// [Rust issue #20671](https://github.com/rust-lang/rust/issues/20671).
///
/// [`Self::Inner`]: FunctorSelf::Inner
type InnerMonad: FunctorSelf<'a>;
/// Generic join
///
/// `.mjoin()` is equivalent to `.bind(|x| x)`.
fn mjoin(self) -> Self::Inner {
self.bind(|x| x)
}
}
impl<'a, T> NestedMonad<'a> for T
where
T: Monad<'a, <Self::Inner as FunctorSelf<'a>>::Inner>,
T: FunctorSelf<'a>,
T::Inner: FunctorSelf<'a>,
T: Functor<
'a,
<Self::Inner as FunctorSelf<'a>>::Inner,
FmapIn = Self::Inner,
Mapped = Self::Inner,
>,
{
type InnerMonad = Self::Inner;
fn mjoin(self) -> Self::Inner {
self.bind(|x| x)
}
}
In Haskell, this seems so much easier.
Maybe it's feasible to use higher's monads and macros or fmap::Monad, but I still have some doubts on usability when things get more complex. I think the main reason is that Rust (for a good reason) imposes a lot of work on the programmer to manually decide when values are cloned, when they are referenced (exclusively or in a shared manner), etc. This could make functional-style programming difficult, I guess.
P.S.: Another practical problem is that closures can't be described as types but only as traits (unless we wrap them in a Box).
