Function returning a closure not working inside my filter

Question

I cannot get this to compile without using a closure. I'm trying to get the function apply to return the correct kind of closure in the first place.

#![feature(conservative_impl_trait)]
#![allow(dead_code)]

fn accumulate<'a>(tuples: &[(&'a str, &Fn(i32) -> bool)], i: i32) {

    // this works
    let _ = tuples.iter().filter(|t| apply(second, i)(t));

    // this doesn't
    //let f = apply(second, i);
    //let _ = tuples.iter().filter(f);

    //this works as well

    let f  = |t: &&(_,_)| apply(second, i)(t);
    let _ = tuples.iter().filter(f);
}

fn apply<A, B, C, F, G>(mut f: F, a: A) -> impl FnMut(B) -> C
         where F: FnMut(B) -> G,
               G: FnMut(A) -> C,
               A: Clone
{
    move |b| f(b)(a.clone())
}


fn second<A, B: ?Sized>(&(_, ref second): &(A, B)) -> &B {
    second
}

fn main()  {}

What can I do to make apply work like I want it to?

Answer 1

First off, let me say that the problem has nothing to do with the use of the impl Trait syntax. I converted the closure to a named struct and got the same results.

So, let's look at the code you'd like to make work:

let f = apply(second, i);
let _ = tuples.iter().filter(f);

What does the compiler have to say about that?

error[E0277]: the trait bound `for<'r> impl std::ops::FnMut<(&(_, _),)>: std::ops::FnMut<(&'r &(&str, &std::ops::Fn(i32) -> bool),)>` is not satisfied
  --> <anon>:11:27
   |
11 |     let _ = tuples.iter().filter(f);
   |                           ^^^^^^ trait `for<'r> impl std::ops::FnMut<(&(_, _),)>: std::ops::FnMut<(&'r &(&str, &std::ops::Fn(i32) -> bool),)>` not satisfied

error[E0277]: the trait bound `for<'r> impl std::ops::FnMut<(&(_, _),)>: std::ops::FnOnce<(&'r &(&str, &std::ops::Fn(i32) -> bool),)>` is not satisfied
  --> <anon>:11:27
   |
11 |     let _ = tuples.iter().filter(f);
   |                           ^^^^^^ trait `for<'r> impl std::ops::FnMut<(&(_, _),)>: std::ops::FnOnce<(&'r &(&str, &std::ops::Fn(i32) -> bool),)>` not satisfied

OK, so we have type X and it needs to implement trait Y but it doesn't. But let's look closely:

for<'r> impl
std::ops::FnMut<(&(_, _),)>:
std::ops::FnMut<(&'r &(_, _),)>

Ah ha! filter expects a function that accepts a reference to a reference to a tuple, whereas the function we're passing in accepts a reference to a tuple. filter passes a reference to a reference because tuples.iter() iterates over references, and filter passes references to these.

Alright, let's change the definition of second to accept references to references:

fn second<'a, A, B: ?Sized>(&&(_, ref second): &&'a (A, B)) -> &'a B {
    second
}

Compiler still not happy:

error[E0277]: the trait bound `for<'r> impl std::ops::FnMut<(&&(_, _),)>: std::ops::FnMut<(&'r &(&str, &std::ops::Fn(i32) -> bool),)>` is not satisfied
  --> <anon>:11:27
   |
11 |     let _ = tuples.iter().filter(f);
   |                           ^^^^^^ trait `for<'r> impl std::ops::FnMut<(&&(_, _),)>: std::ops::FnMut<(&'r &(&str, &std::ops::Fn(i32) -> bool),)>` not satisfied

error[E0271]: type mismatch resolving `for<'r> <impl std::ops::FnMut<(&&(_, _),)> as std::ops::FnOnce<(&'r &(&str, &std::ops::Fn(i32) -> bool),)>>::Output == bool`
  --> <anon>:11:27
   |
11 |     let _ = tuples.iter().filter(f);
   |                           ^^^^^^ expected bound lifetime parameter , found concrete lifetime
   |
   = note: concrete lifetime that was found is lifetime '_#24r

expected bound lifetime parameter , found concrete lifetime... What does that mean?

f's type is some type that implements FnMut(&'c &'b (&'a str, &Fn(i32) -> bool)) -> bool. In the call to apply, B == &'c &'b (&'a str, &Fn(i32) -> bool) and C == bool. Note that B is one fixed type here; 'c represents one, fixed lifetime, which is called a concrete lifetime.

Let's take a look at filter's signature:

fn filter<P>(self, predicate: P) -> Filter<Self, P> where
    Self: Sized, P: FnMut(&Self::Item) -> bool,

Here, P must implement FnMut(&Self::Item) -> bool. Actually, this syntax is shorthand for for<'r> FnMut(&'r Self::Item) -> bool. Here. 'r is a bound lifetime parameter.

So, the problem is that our function that implements FnMut(&'c &'b (&'a str, &Fn(i32) -> bool)) -> bool does not implement for<'r> FnMut(&'r Self::Item) -> bool. We'd need a function that implements for<'c> FnMut(&'c &'b (&'a str, &Fn(i32) -> bool)) -> bool. The only way to do this, for now, would be to write apply like this:

fn apply<A, B, C, F, G>(mut f: F, a: A) -> impl FnMut(&B) -> C
         where F: FnMut(&B) -> G,
               G: FnMut(A) -> C,
               A: Clone
{
    move |b| f(b)(a.clone())
}

or the more explicit version:

fn apply<A, B, C, F, G>(mut f: F, a: A) -> impl for<'r> FnMut(&'r B) -> C
         where F: for<'r> FnMut(&'r B) -> G,
               G: FnMut(A) -> C,
               A: Clone
{
    move |b| f(b)(a.clone())
}

If Rust eventually supports higher-kinded types, there might be a more elegant way to solve this problem.