Guess the language by the error

[sassa_nf]

This is what happens from trying to be too clever:

error[E0310]: the parameter type `A` may not live long enough
  --> src/main.rs:8:4
   |
7  |   fn succ<A>(n : Box<Nat<A>>) -> Box<Nat<A>> {
   |           - help: consider adding an explicit lifetime bound `A: 'static`...
8  | /    Box::new(move |f| {
9  | |       let g = n(Box::new(f));
10 | |       Box::new(move |x| f(g(x)))
11 | |    })
   | |_____^

Why the heck does it want A to survive? I thought that's declarative and has no meaning at run time?

error[E0382]: use of moved value: `f`
  --> src/main.rs:10:16
   |
8  |    Box::new(move |f| {
   |                   - move occurs because `f` has type `std::boxed::Box<dyn std::ops::Fn(u32) -> u32>`, which does not implement the `Copy` trait
9  |       let g = n(Box::new(f));
   |                          - value moved here
10 |       Box::new(move |x| f(g(x)))
   |                ^^^^^^^^ - use occurs due to use in closure
   |                |
   |                value used here after move

Pretty tough luck, eh?..

All I wanted was:

type Nat<A> = dyn Fn(Box<dyn Fn(A) -> A>) -> Box<dyn Fn(A) -> A>;
  
fn zero<A>(_f : Box<dyn Fn(A) -> A>) -> Box<dyn Fn(A) -> A> {
   Box::new(|x| x)
}

fn succ<A>(n : Box<Nat<A>>) -> Box<Nat<A>> {
   Box::new(move |f| {
      let g = n(f);
      Box::new(move |x| f(g(x)))
   })
}

But each Fn is a closure with the whole environment, where the environment is not guaranteed to be cloneable. It can't be a fn (the function without environment), because it is meant to capture at least n. And it can't be a reference, because what's the lifetime of the returned value?

But that is not even what I want. What I really want is

type Nat = dyn Fn(Box<dyn Fn<A>(A) -> A>) -> Box<dyn Fn<A>(A) -> A>;

That is, the function passed in must be polymorphic on the type, not Nat. In order to be able to:

fn add<A: 'static>(m: Box<Nat<A>>, n: Box<Nat<A>>) -> Box<Nat<A>> {
   Box::new( m(Rc::new(succ)) ( n )) // Eh.... well.... I actually mean Nat works with any type, not one fixed type
}

But that, of course, is not even possible.

(Well, and the Rc slipping through means I know what's wrong with closure cloning)

Comments

[juan_gandhi]

I wonder if it's possible in Rust.

[sassa_nf]

Well, I figured the Box<dyn Fn...> is not enough - succ needs to use f twice, and that means the context captured by f needs cloning to create Box twice. But using Rc (ref counting boxing) seems to solve that (I still need to let that soak in). Then using <A:'static> for the limitation of succ stops the complaining, but not clear what is meant there. Is it possible to for types that are not 'static to exist?..

But the last puzzle perhaps has no solution.