I recently added applicative functors to the `fmap`

crate. After almost ending up in an endless loop in my mind , I think I managed to trick the compiler into an endless loop:

```
pub trait Functor<'a, B>
where
Self: Sized,
B: 'a,
{
type Inner: 'a;
type Mapped: Functor<'a, B, Inner = B, Mapped = Self::Mapped>
+ Functor<'a, Self::Inner, Inner = B, Mapped = Self>;
fn fmap<F>(self, f: F) -> Self::Mapped
where
F: 'a + Send + FnMut(Self::Inner) -> B;
}
pub trait Pure<'a, B>
where
Self: Functor<'a, B>,
B: 'a,
{
fn pure(b: B) -> Self::Mapped;
}
pub trait Monad<'a, B>
where
Self: Pure<'a, B>,
B: 'a,
{
fn bind<F>(self, f: F) -> Self::Mapped
where
F: 'a + Send + FnMut(Self::Inner) -> Self::Mapped;
}
pub type BoxMapper<'a, T, B> =
Box<dyn 'a + Send + FnMut(<T as Functor<'a, B>>::Inner) -> B>;
pub trait MonadWithMapper<'a, B>
where
Self: Monad<'a, B>,
Self: Pure<'a, BoxMapper<'a, Self, B>>,
B: 'a,
{
type MapperMonad: Functor<
'a,
B,
Inner = BoxMapper<'a, Self, B>,
Mapped = <Self as Functor<'a, B>>::Mapped,
> + Monad<'a, B>
+ Pure<'a, BoxMapper<'a, Self, B>>;
}
impl<'a, T, B> MonadWithMapper<'a, B> for T
where
T: Monad<'a, B>,
T: Pure<'a, BoxMapper<'a, T, B>>,
<T as Functor<'a, BoxMapper<'a, T, B>>>::Mapped: Functor<
'a,
B,
Inner = BoxMapper<'a, T, B>,
Mapped = <T as Functor<'a, B>>::Mapped,
> + Monad<'a, B>
+ MonadWithMapper<'a, B> // this line causes the build process to never terminate
+ Pure<'a, BoxMapper<'a, T, B>>,
B: 'a,
{
type MapperMonad = <T as Functor<'a, BoxMapper<'a, T, B>>>::Mapped;
}
pub fn monad_apply<'a, T, B>(
monad: T,
f: T::MapperMonad,
) -> <T as Functor<'a, B>>::Mapped
where
T: 'a + Send + Clone,
T: MonadWithMapper<'a, B>,
{
f.bind(move |inner| monad.clone().fmap(inner))
}
impl<'a, A, B> Functor<'a, B> for Vec<A>
where
A: 'a,
B: 'a,
{
type Inner = A;
type Mapped = Vec<B>;
fn fmap<F>(self, f: F) -> Self::Mapped
where
F: 'a + Send + FnMut(Self::Inner) -> B,
{
self.into_iter().map(f).collect()
}
}
impl<'a, A, B> Pure<'a, B> for Vec<A>
where
A: 'a,
B: 'a,
{
fn pure<'b>(b: B) -> Self::Mapped {
vec![b]
}
}
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(Self::Inner) -> Self::Mapped,
{
let mut vec = Vec::new();
for item in self.into_iter() {
for item in f(item).into_iter() {
vec.push(item);
}
}
vec
}
}
fn main() {
let f: Vec<Box<dyn Send + FnMut(i32) -> i32>> =
vec![Box::new(|x| x), Box::new(|x| x * 100)];
let a = vec![4, 7, 9];
let b = monad_apply(a, f);
assert_eq!(b, vec![4, 7, 9, 400, 700, 900]);
}
```

Errors:

```
Compiling playground v0.0.1 (/playground)
/playground/tools/entrypoint.sh: line 11: 9 Killed timeout --signal=KILL ${timeout} "$@"
```

The line that causes the problem is this one:

```
+ MonadWithMapper<'a, B> // this line causes the build process to never terminate
```

And it will only cause problems when the `main`

function is compiled.

I'm not entirely sure if the compiler is stuck in an endless loop or whether it ran into exponential complexity or if there is some other problem.

P.S.: I tested with `rustc 1.72.0-nightly (371994e0d 2023-06-13)`

, but the stable compiler on Playground seems to get stuck too.