Functional Programming: What type to return?

this one works well

fn get_fun() -> impl Fn() -> usize {
    || 42
}

but what type to return in following function

fn get_fun2() -> ??? {
    || { || 42 }
}

i've tried impl Fn() -> (impl Fn() -> usize) but it doesn't work,
Can someone explain it to me, why it doesn't work, and how to solve it?
Thanks

I know the problem isn't about life time, because this code compiles

fn main() {
    let a;
    {
        a = || { || 42 };
    }
    println!("{}", a()())
}

and also, how to move it to another function?

fn main() {
    let a;
    {
        a = || { || 42 };
    }
    do_it(a);
}

fn do_it(f: ???) {
    println!("{}", f()())
}

It would be very useful if you could post some error messages

Sorry, I didn't include that

error[E0562]: `impl Trait` not allowed outside of function and inherent method return types
  --> src/main.rs:77:31
   |
77 | fn get_fun2() -> impl Fn() -> (impl Fn() -> usize) {
   |                                ^^^^^^^^^^^^^^^^^^

Unfortunately, nested impl Trait like that isn’t supported. At some perf cost, you can box the nested closure:

fn get_fun() -> impl Fn() -> Box<dyn Fn() -> usize> {
   || Box::new(|| 42)
}
4 Likes

Ah @vitalyd was faster to reply, anyway, here's a full example on the playground:

It seems the box is necessary because functions are not Sized (according to compiler errors i got when making this)

You could also use function pointers (fn) to get a similar result and not have to worry about traits like FnMut or stuff, just take a mutable reference to the fn
Playground

1 Like

Thanks for the answers,

Yeah, as I thought.
Currently, it is impossible to create a closure that returns other closure without allocating memory in heap.

Why I think this is possible because returning closure doesn't need allocating memory in heap, closure returning another closure is still a closure.

Conside following code

/*
in haskell:

get_fun2 = \() -> \() -> \() -> 42
do_it f = print(f()())
a = get_fun2()
do_it(a)
*/

struct Closure1(usize);
impl Closure1 {
    fn call(&self) -> usize {
        self.0
    }
}

struct Closure2(Closure1);
impl Closure2 {
    fn call(&self) -> &Closure1 {
        return &self.0
    }
}

fn get_fun2() -> Closure2 {
    Closure2(Closure1(42))
}

fn do_it(c: Closure2) {
    println!("{}", c.call().call())
}

fn main() {
    let a = get_fun2();
    do_it(a);
}

in that code, we pretend Closure1 and Closure2 are generated by the compiler, as you can see, it is possible to create a closure that returning another closure without needing for allocating memory in heap.

It is just, it is not possible to express it as impl Trait

That's right, currently you need to state auxiliary structs. I had the same issue a few weeks ago:

How to curry more than one argument?

You can do that with a custom trait:

trait NestedClosure {
    type Output: Fn() -> usize;
    fn call(&self) -> Self::Output;
}

impl<R, T> NestedClosure for T
where
    R: Fn() -> usize,
    T: Fn() -> R,
{
    type Output = R;
    fn call(&self) -> Self::Output {
        self()
    }
}

fn get_fun2() -> impl NestedClosure {
    || || 42
}

fn main() {
    let x = get_fun2();
    println!("{}", x.call()());
}

(playground)

This has some limitations: you have to use x.call() instead of just x(), and you'll need a separate trait for each number of arguments and each level of nesting. The trait can be generic over function arguments and return value, though.

If you are fine with using nightly, then you could do this

#![feature(unboxed_closures)]

fn ret() -> impl Fn<(), Output = impl Fn<(), Output = u32>> {
    || || 4
}

fn hi() {
    let r = ret();
    assert_eq(r()(), 4);
}
1 Like