Applicative functors: Compiler hangs when adding a bound

I recently added applicative functors to the fmap crate. After almost ending up in an endless loop in my mind :face_with_spiral_eyes:, I think I managed to trick the compiler :robot: 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]);
}

(Playground)

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.

Lol, feels like this code is screaming at me, “'a 'a 'a 'a 'a 'a 'a 'a 'a 'a 'a 'a …”hhh!

Gotta love lifetimes :sweat_smile:

Honestly though, I’m very fond of explorations for representing these type classes traits in Rust, (as I’ve done so myself, a little bit, in the past), I’ll take a note to look at the crate (and the possibly-infinite-loop for compilation) in the next few days.

Regarding approaches to learn more about the issue (of hanging compilation), it might help trying to minimize the problem. If minimization works, it might also offer better insights into whether it’s truly infinitely hanging or just exponentially slow, as with minimization, slow things tend to get faster, whereas hanging things keep hanging… at least if we’re lucky (and successful) :slight_smile: If you haven’t already by the time I look at it, I might give minimization a try myself, too ^^

Well, I have been trying some back-and-forth scenarios to get rid of the lifetimes and/or bounds, but if I want to accept non-static mapping functions and lazy evaluation, I feel like I need at least one lifetime everywhere (e.g. to support Box<dyn 'non_static + Iterator> being returned by Functor::fmap). I tried to put the lifetimes in GAT's, but this didn't really make things better.

Ooooo'bs, I just noticed there is an unused lifetime 'b in my code yet (I had even more lifetimes in past):

    fn pure<'b>(b: B) -> Self::Mapped {
        vec![b]
    }

(But that's entirely unrelated to the problem.)

Side note because I saw you used GATs:

In order to support types which put additional bounds (like Eq + Hash) on functors (e.g. HashSet), I finally refrained from using GATs altogether. My approach uses type parameters only. I'm a bit surprised myself that I didn't use GATs (e.g. here) in the end.

If you have any issues following the design choices, feel free to ask. I'm happy about feedback. This crate got me a lot of headache, and I was seriously feeling like ending up in an endless thought loop at times.

Well, I already tried to only copy the parts that are needed for demonstration of the problem and removed all the other traits of the crate. But I admit it's still a lot of code left. It's a bit difficult to remove things because they all depend on each other, but I will also give it a try to minimize the example further.


I tried to minimize it, and got this far. The following code still exhibits the (allegedly) endless loop:

pub trait Functor<B> {
    type Inner;
    type Mapped;
}

pub type BoxMapper<T, B> =
    Box<dyn Send + FnMut(<T as Functor<B>>::Inner) -> B>;

pub trait MonadWithMapper<B>
where
    Self: Functor<B>,
    Self: Functor<BoxMapper<Self, B>>,
{
    type MapperMonad: Functor<
            B,
            Inner = BoxMapper<Self, B>,
            Mapped = <Self as Functor<B>>::Mapped,
        >;
}

impl<T, B> MonadWithMapper<B> for T
where
    T: Functor<B>,
    T: Functor<BoxMapper<T, B>>,
    <T as Functor<BoxMapper<T, B>>>::Mapped: Functor<
            B,
            Inner = BoxMapper<T, B>,
            Mapped = <T as Functor<B>>::Mapped,
        >
        + MonadWithMapper<B>, // this line causes the build process to never terminate
{
    type MapperMonad = <T as Functor<BoxMapper<T, B>>>::Mapped;
}

pub fn monad_apply<T, B>(
    monad: T,
) -> <T as Functor<B>>::Mapped
where
    T: MonadWithMapper<B>,
{
    todo!()
}

impl<A, B> Functor<B> for Vec<A>
where
{
    type Inner = A;
    type Mapped = Vec<B>;
}

fn main() {
    monad_apply(Vec::<i32>::new());
}

(Playground)

When I try to get rid of Inner, I get this weird error:

 pub trait Functor<B> {
-    type Inner;
     type Mapped;
 }
 
-pub type BoxMapper<T, B> =
-    Box<dyn Send + FnMut(<T as Functor<B>>::Inner) -> B>;
+pub type BoxMapper<B> =
+    Box<dyn Send + FnMut() -> B>;
 
 pub trait MonadWithMapper<B>
 where
     Self: Functor<B>,
-    Self: Functor<BoxMapper<Self, B>>,
+    Self: Functor<BoxMapper<B>>,
 {
     type MapperMonad: Functor<
             B,
-            Inner = BoxMapper<Self, B>,
             Mapped = <Self as Functor<B>>::Mapped,
         >;
 }
 
 impl<T, B> MonadWithMapper<B> for T
 where
     T: Functor<B>,
-    T: Functor<BoxMapper<T, B>>,
-    <T as Functor<BoxMapper<T, B>>>::Mapped: Functor<
+    T: Functor<BoxMapper<B>>,
+    <T as Functor<BoxMapper<B>>>::Mapped: Functor<
             B,
-            Inner = BoxMapper<T, B>,
             Mapped = <T as Functor<B>>::Mapped,
         >
         + MonadWithMapper<B>, // this line causes the build process to never terminate
 {
-    type MapperMonad = <T as Functor<BoxMapper<T, B>>>::Mapped;
+    type MapperMonad = <T as Functor<BoxMapper<B>>>::Mapped;
 }
 
 pub fn monad_apply<T, B>(
     monad: T,
 ) -> <T as Functor<B>>::Mapped
 where
     T: MonadWithMapper<B>,
 {
     todo!()
 }
 
 impl<A, B> Functor<B> for Vec<A>
 where
 {
-    type Inner = A;
     type Mapped = Vec<B>;
 }
 
 fn main() {
     monad_apply(Vec::<i32>::new());
 }

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0275]: overflow evaluating the requirement `Box<(dyn FnMut() -> _ + Send + 'static)>: Sized`
  --> src/main.rs:48:5
   |
48 |     monad_apply(Vec::<i32>::new());
   |     ^^^^^^^^^^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`playground`)
note: required for `Vec<Box<(dyn FnMut() -> _ + Send + 'static)>>` to implement `Functor<Box<(dyn FnMut() -> _ + Send + 'static)>>`
  --> src/main.rs:41:12
   |
41 | impl<A, B> Functor<B> for Vec<A>
   |         -  ^^^^^^^^^^     ^^^^^^
   |         |
   |         unsatisfied trait bound introduced here
note: required for `Vec<Box<(dyn FnMut() -> _ + Send + 'static)>>` to implement `MonadWithMapper<_>`
  --> src/main.rs:19:12
   |
19 | impl<T, B> MonadWithMapper<B> for T
   |            ^^^^^^^^^^^^^^^^^^     ^
...
25 |             Mapped = <T as Functor<B>>::Mapped,
   |             ---------------------------------- unsatisfied trait bound introduced here
   = note: 127 redundant requirements hidden
   = note: required for `Vec<i32>` to implement `MonadWithMapper<_>`
note: required by a bound in `monad_apply`
  --> src/main.rs:36:8
   |
32 | pub fn monad_apply<T, B>(
   |        ----------- required by a bound in this function
...
36 |     T: MonadWithMapper<B>,
   |        ^^^^^^^^^^^^^^^^^^ required by this bound in `monad_apply`

For more information about this error, try `rustc --explain E0275`.
error: could not compile `playground` (bin "playground") due to previous error

It still doesn't feel "minimal" yet, but at least it's a bit smaller now (and doesn't have all these 'a lifetimes anymore).

I was able to minimize further:

Code
pub trait Functor<B> {
    type Inner;
    type Mapped;
}

pub type BoxMapper<T, B> =
    &'static dyn FnMut(<T as Functor<B>>::Inner) -> B; // hangs
    //&'static fn(<T as Functor<B>>::Inner) -> B; // gives error

pub trait MonadWithMapper<B> {}

impl<T, B> MonadWithMapper<B> for T
where
    T: Functor<B>,
    T: Functor<BoxMapper<T, B>>,
    <T as Functor<BoxMapper<T, B>>>::Mapped: MonadWithMapper<B>,
{
}

pub fn monad_apply<T, B>()
where
    T: MonadWithMapper<B>,
{
}

impl<A, B> Functor<B> for A {
    type Inner = A;
    type Mapped = B;
}

fn main() {
    monad_apply::<(u8, u8), u8>();
}

(Playground)

Errors:

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


Update: And I was able to get rid of the Inner type too:

pub trait Functor<B> {
    type Mapped;
}

pub type BoxMapper<T, B> =
    &'static dyn FnMut(T) -> B; // hangs
    //&'static fn(T) -> B; // gives error

pub trait MonadWithMapper<B> {}

impl<T, B> MonadWithMapper<B> for T
where
    T: Functor<BoxMapper<T, B>>,
    <T as Functor<BoxMapper<T, B>>>::Mapped: MonadWithMapper<B>,
{
}

pub fn monad_apply<T, B>()
where
    T: MonadWithMapper<B>,
{
}

impl<A, B> Functor<B> for A {
    type Mapped = B;
}

fn main() {
    monad_apply::<(i32, i32), i32>();
}

(Playground)

2 Likes

I simplified the code further and opened an issue (#113359).

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.