Functional Programming: What type to return?

[win-t]

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

[win-t]

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

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

[win-t]

and also, how to move it to another function?

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

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

[TheZoq2]

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

[win-t]

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) {
   |                                ^^^^^^^^^^^^^^^^^^

[vitalyd]

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

[mmmmib]

Ah @vitalyd was faster to reply, anyway, here’s a full example on the playground:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=b79dc596b1524f72582a7b68d394972d
It seems the box is necessary because functions are not Sized (according to compiler errors i got when making this)

[OptimisticPeach]

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

[win-t]

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

[JohnBSmith]

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?

[Riateche]

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.

[KrishnaSannasi]

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