How to express the trait bounds of a generic method when implementing a trait that requires this method to exist?

Question

General Question

I do have a struct that requires a type constraint on a generic method in its impl block. When implementing a foreign trait, I would like to rely on the presence of said method.

Is there some workaround in Rust, that allows to express the limitations on a generic method at the impl level?

I would imagine something like Higher Ranked Trait Bounds, but for types, not lifetimes? Think: "For all types B, condition has to hold."

In Pseudocode:

struct A{};
impl A {
    fn constrained<B,F>(p : F) where F : Fn(A)->B, SomeConstraint<B>{
        ...
    }
}
impl SomeTrait for A where "the method constrained() exists" {
    ...
}

Edit: It seems I'm not the only person looking for this functionality. There recently has been a Major Change Proposal to "Add experimental support for for<T> binders in limited positions". Also, the implementation work has already started it seems, as "Implement partial support for non-lifetime binders" has been merged some days ago.

My concrete problem

I'm currently playing around with higher, and would like to try to implement the Free Monad type based on it. This is mostly for me to learn about generics in Rust, not aimed at any actual use case. In addition, I would like to do the implementation using only generics, not macros.

As explained above, I now have a type, that has a generic method, which needs trait bounds based on the method's own type parameters.

I'd like to use this method in the implementation of a foreign trait (Functor, for instance), and I can't come up with a reasonable way to express the method's trait bounds at this level.

Here is the code I have, as far as I managed to have it working:

enum Free<'a,A,F> where F : Functor<'a,Never>{
    Pure(A),
    Free(Box<F::Target<Self>>)
}
impl<'a,A,G> Free<'a,A,G> where G : Functor<'a,Never>{
    fn __fmap_impl<B, F>(self, f: &'a F) -> Free<'a,B,G> where F: Fn(A) -> B + 'a, G::Target::<Self> : Functor<'a, Self, Target<Free<'a,B,G>> = G::Target<Free<'a,B,G>>>{
        match self {
            Free::Pure(a) => {Free::Pure(f(a))},
            Free::Free(fa) => {
                Free::<'a,B,G>::Free(Box::new(
                    fa.fmap(|x| x.__fmap_impl(f))
                ))
            },
        }
    }
}

The usage of Never is to avoid infinite recursion in the Free type... I'm using the GAT of Functor to replace Never with the actual type it wraps.

Here's a playground, with a usage example to prove it compiles.

The problem I'm now facing is the bound on the method __fmap_impl().

If I try to implement the actual Functor trait for Free, I have no way to express the constraint:

impl<'a,A,G> Functor<'a,A> for Free<'a,A,G> where G:Functor<'a,Never>{
    type Target<T> = Free<'a,T,G>;

    fn fmap<B, F>(self, f: F) -> Self::Target<B>
        where
        F: Fn(A) -> B + 'a,
        G::Target::<Self> : Functor<'a, Self, Target<Free<'a,B,G>> = G::Target<Free<'a,B,G>>>
    {
           self.__fmap_impl(&f)
    }
}

Non-compiling playground.

This yields:

error[E0276]: impl has stricter requirements than trait

I can't move the bound from fmap to the impl because there B is not known, and if I try to add it, I would get

error[E0207]: the type parameter B is not constrained by the impl trait, self type, or predicates

impl<'a,A,B,G> Functor<'a,A> for Free<'a,A,G> where G:Functor<'a,Never>, G::Target::<Self> : Functor<'a, Self, Target<Free<'a,B,G>> = G::Target<Free<'a,B,G>>>{
    type Target<T> = Free<'a,T,G>;

    fn fmap<C, F>(self, f: F) -> Self::Target<C>
        where
        F: Fn(A) -> C + 'a
    {
           self.__fmap_impl(&f)
    }
}

(Playground, once more)

If there were a way to use Higher Ranked Trait Bounds with types, the above could be solved, because for a well behaved Functor, the condition G:Functor<'a,Never>, G::Target::<Self> : Functor<'a, Self, Target<Free<'a,B,G>> = G::Target<Free<'a,B,G>>> should be true for all possible types B (unless I misunderstood something)...

I guess, I'm just approaching the problem from the wrong angle. Any input on how to solve this is welcome.

Answer 1

I immediately should have tried #![feature(non_lifetime_binders)] after I learned about it, instead of editing the question.

This unstable feature indeed solves the problem:

#![feature(non_lifetime_binders)]
impl<'a,A,G> Functor<'a,A> for Free<'a,A,G>
    where G : Functor<'a,Never>,
    for<B> G::Target::<Self> :
       Functor<'a, Self, Target<Free<'a,B,G>> = G::Target<Free<'a,B,G>>>
{
    type Target<T> = Free<'a,T,G>;
    fn fmap<C, F>(self, f: F) -> Self::Target<C> where F: Fn(A) -> C + 'a{
        self.__fmap_impl(std::rc::Rc::new(f))
    }
}

Playground that compiles with Nightly

Other answers, that work with Stable, would still be welcome, of course.