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
– rodrigo, Commented Oct 3, 2018 at 8:16
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. — 周汉成
– 周汉成, Commented Oct 3, 2018 at 12:40
What I want is: play.rust-lang.org/?gist=044651be795dc090ce740e7ca6f7a437 — 周汉成
– 周汉成, Commented Oct 3, 2018 at 13:17
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
– rodrigo, Commented Oct 3, 2018 at 13:21
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 — 周汉成
– 周汉成, Commented Oct 3, 2018 at 13:28

rodrigo · Accepted Answer · 2018-10-05 09:45:35Z

1

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));
}

answered Oct 5, 2018 at 9:45

rodrigo

99.3k13 gold badges162 silver badges205 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

周汉成 Over a year ago

In your first comment, removing the Box, I don't see any dynamic references,fn b (c: impl Fn(u64) -> u64, n: u64) just works out, why?

rodrigo Over a year ago

@周汉成: Ah, but the code in that comment does have a dynamic reference. You don't see it because the type is deduced by the compiler: the f argument in the lambda function. If you check its type, it is &dyn Fn(_) -> _. Which is expected, because that is what fix() needs.

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related