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>

Just removing the Box seems to work for me. Is that what you want? — rodrigo
It works for me too. But I found what I need is still more complex than it. I don't know whether I need to take a break, or keep asking question. I'm new to Rust, and I'm tired. — 周汉成
What I want is: play.rust-lang.org/?gist=044651be795dc090ce740e7ca6f7a437 — 周汉成
It looks like you are mixing fn, dyn Fn and maybe impl Fn. I'm not familiar with tool but messing around, this version compiles. — rodrigo
I will learn them soon, Hi I change the gist just now when you are helping me. Shall you check it again: play.rust-lang.org/?gist=044651be795dc090ce740e7ca6f7a437 — 周汉成

rodrigo rodrigo · Accepted Answer · 2018-10-05T09:45:35

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

fn(A) -> B
impl Fn(A) -> B or T: Fn(A) -> B
&dyn Fn(A) -> B
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));
}

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

1 Answers