Recursive closure as function parameter “cannot infer an appropriate lifetime due to conflicting requirements”

Question

This question is more complex than Closure as function parameter “cannot infer an appropriate lifetime due to conflicting requirements”.

There's a recursive closure which move environmental variable into it.

The code below works, tool is a grab-bag of useful functions for functional programming includes making recursive closure:

extern crate tool;
use tool::prelude::*;
use std::cell::Cell;

fn main() {
    let a = Cell::new(false);

    let fib = fix(move |f, x| {
        a.set(true);
        if x == 0 || x == 1 {
            x
        } else {
            // `f` is `fib`
            f(x - 1) + f(x - 2)
        }
    });

    println!("{}", fib(10));
}

I want to know is it possible to pass that closure to a function, then call that function in that closure, the code below throws an error.

extern crate tool;
use tool::prelude::*;
use std::cell::RefCell;

fn main() {
    let a = RefCell::new(false);

    let fib = fix(move |f, x| {
        *a.borrow_mut() = true;
        if x == 0 || x == 1 {
            x
        } else {
            // `f` is `fib`
            b(Box::new(f), x - 1) + f(x - 2)
        }
    });

    fn b (c: Box<Fn(u64) -> u64>, n: u64) -> u64 {
        c(n)
    }

    println!("{}", b(Box::new(fib), 10));
}

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
  --> src/main.rs:14:24
   |
14 |             b(Box::new(f), x - 1) + f(x - 2)
   |                        ^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #2 defined on the body at 8:19... 
  --> src/main.rs:8:19
   |
8  |       let fib = fix(move |f, x| {
   |  ___________________^
9  | |         *a.borrow_mut() = true;
10 | |         if x == 0 || x == 1 {
11 | |             x
...  |
15 | |         }
16 | |     });
   | |_____^
   = note: ...so that the expression is assignable:
           expected &dyn std::ops::Fn(u64) -> u64
              found &dyn std::ops::Fn(u64) -> u64
   = note: but, the lifetime must be valid for the static lifetime...
   = note: ...so that the expression is assignable:
           expected std::boxed::Box<(dyn std::ops::Fn(u64) -> u64 + 'static)>
              found std::boxed::Box<dyn std::ops::Fn(u64) -> u64>

Answer 1

It looks like you are mixing several concepts here. First of all you must understand the difference between these:

1. fn(A) -> B
2. impl Fn(A) -> B or T: Fn(A) -> B
3. &dyn Fn(A) -> B
4. Box<dyn Fn(A) -> B>

Number 1 is the type of a pointer to a function, just like in C.

Number 2 is a generic type that implements the function trait Fn, that is a type that is callable.

Number 3 is a dynamic reference to a callable object (the dyn keyword is optional).

Number 4 is a trait object, that is a boxed callable object with the real type erased.

Now look at the definition of tool::fix:

pub fn fix<A, B, F>(f: F) -> impl Fn(A) -> B 
where
    F: Fn(&Fn(A) -> B, A) -> B, 

From that you see that fix uses number 2 for the f parameter, but number 3 for the A parameter of f. Also, it returns number 2.

The tricky part here is that f is a function that takes a function as argument. The f itself can be any of any kind that implements Fn, but the first argument of that function must be of &dyn Fn kind.

Your original error comes from trying to box a &dyn Fn(A) -> B, but you cannot do that generically, because such a value may contain references, and Box requires a 'static type.

But with all that in mind you can carefully write your function without using Box, so your problem just disappears, and the result is nicer (playground):

fn main() {
    fn wrap (wrap_fn: impl Fn(&dyn Fn(u64) -> u64, u64) -> u64) -> impl Fn(u64) -> u64 {
        let a = RefCell::new(false);

        let fib = fix(move |f, x| {
            *a.borrow_mut() = true;
            if x == 0 || x == 1 {
                x
            } else {
                // `f` is `fib`
                wrap_fn(f, x - 1) + wrap_fn(f, x - 2)
            }
        });  

        fib
    }

    fn b (c: &dyn Fn(u64) -> u64, n: u64) -> u64 {
        c(n)
    }

    println!("{}", (wrap(b))(10));
}