How write a function that returns itself?

[Fancyflame]

This is not a practical application, I just want to know whether Rust could acheive this or not. I think it can be done in physics, but not sure whether it violates Rust's type system.

I tried using a helper trait but failed.

trait SelfFn: (Fn() -> Self) + 'static {}
impl<T> SelfFn for T where T: (Fn() -> Self) + 'static {}

fn a() -> impl SelfFn {
    a
}

it doesn't compiles

error[E0275]: overflow evaluating the requirement `<fn() -> impl SelfFn {a} as FnOnce<()>>::Output == fn() -> impl SelfFn {a}`
 --> src/lib.rs:4:11
  |
4 | fn a() -> impl SelfFn {
  |           ^^^^^^^^^^^
  |
note: required for `fn() -> impl SelfFn {a}` to implement `SelfFn`
 --> src/lib.rs:2:9
  |
2 | impl<T> SelfFn for T where T: (Fn() -> Self) + 'static {}
  |         ^^^^^^     ^                   ---- unsatisfied trait bound introduced here

For more information about this error, try `rustc --explain E0275`.

Is there a way to achieve this is stable Rust?

[Michael-F-Bryan]

I suspect this is impossible without adding another level of indirection.

If you were to remove the impl SelfFn and write out the actual type being returned, what would you put in there? You'd say that a returns a function that returns a function that returns a function that returns a... Ad infinitum.

It's kinda like when a type contains itself, so the compiler can't figure out how big it'll be. A trivial example is when you try to define a node in a linked list:

struct Node {
 value: String,
  next: Option<Node>,
}

In that situation, the solution is to put a box around the Node.

For your situation, you'll need type erasure to remove the infinite recursion when figuring out what a actually returns.

Maybe something like this?

trait SelfFn {
    fn call(&self) -> Box<dyn SelfFn>;
}

impl<F> SelfFn for F
where
    F: Fn() -> Box<dyn SelfFn>,
{
    fn call(&self) -> Box<dyn SelfFn> {
        self()
    }
}

fn a() -> Box<dyn SelfFn> {
    Box::new(a)
}

(Playground)

[Fancyflame]

I got your point, thanks, but your workaround doesn't completely match the question. The final structure or function is required to implements Fn() -> Self, so that it can be called like this:

func()()()().....()();

but yours will be look like:

func.call().call().call()......call().call();

And, with an extra Box layer, it caused an extra allocation overhead.
If so, obviously we have a better and widely used solution, the builder pattern.

struct F;
impl F {
  fn call(self) -> Self {
    self
  }
}

fn main() {
  F.call().call().call().call();
}

[steffahn]

Here's a fun approach using a newtype with a deref impl

struct SelfFn(fn() -> SelfFn);

fn a() -> SelfFn {
    SelfFn(a)
}

impl std::ops::Deref for SelfFn {
    type Target = fn() -> SelfFn;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

fn main() {
    a()()()()()()();
}

Rust Playground

It doesn't actually make the type implement Fn, but the function call syntax still works at least.

[Fancyflame]

Yes, it did "looks and acts like a function", but it is a camouflage, not a type actually implements Fn() -> Self. I wonder if there is a better way.

[steffahn]

As a fun exercise, I've asked ChatGPT for help to turn this into a fun representation of DFAs. Letting it take the example from wikipedia

We can get something like

struct SelfFn(fn(bool) -> SelfFn);

fn s0(input: bool) -> SelfFn {
    println!("State S0, Input {}", input as u8);
    if input {
        println!("Next state will be S1");
        SelfFn(s1)
    } else {
        println!("Staying in state S0");
        SelfFn(s0)
    }
}

fn s1(input: bool) -> SelfFn {
    println!("State S1, Input {}", input as u8);
    if input {
        println!("Next state will be S0");
        SelfFn(s0)
    } else {
        println!("Next state will be S2");
        SelfFn(s2)
    }
}

fn s2(input: bool) -> SelfFn {
    println!("State S2, Input {}", input as u8);
    if input {
        println!("Staying in state S2");
        SelfFn(s2)
    } else {
        println!("Next state will be S1");
        SelfFn(s1)
    }
}

impl std::ops::Deref for SelfFn {
    type Target = fn(bool) -> SelfFn;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

fn main() {
    s0(true)(false)(false)(true);
}

Rust Playground

State S0, Input 1
Next state will be S1
State S1, Input 0
Next state will be S2
State S2, Input 0
Next state will be S1
State S1, Input 1
Next state will be S0

[quinedot]

You can do it non-generically on nightly.

[Fancyflame]

A new and interesting knowledge for me, even if it doesn't seem related to the topic.

[Fancyflame]

Although the question is how to do it with stable rust, this workaround is the best for now.

[quinedot]

Not itself but here's a fun one using TAIT.