Type for a function which accepts itself

I just got a funny problem. I want to describe a type for a function which accepts itself as an argument (through Fn trait). And I realized I can't write it.

fn foo(arg: impl Fn( ???) -> ()){
}

Can it be solved in a straightforward manner?

What problem are you trying to solve to come up with that solution? You're basically setting up 2 mirrors opposite to each other and trying to look for what's beyond the reflection.

Rust decided in Tracking issue for closure types that reference themselves · Issue #46062 · rust-lang/rust · GitHub that this is not allowed for a closure to reference its own type.

I remember it since it was very brefly (ab)used in a fixpoint combinator Revert the fix function back to its odds 0.2.x shape by bluss · Pull Request #24 · bluss/odds · GitHub The odds crate is basically deprecated. But you could look at its Fix type for inspiration.

2 Likes

There is no problem to solve, I've just played with trait objects and found this puzzle. I stripped away 'dyn' part, and got to the simplest scope I can. It is a funny (in my opinion) exercise in types.

You can call one monomorphized version of yourself with a different monomorphized version of yourself:

fn f<T, F: Fn(T)>(_: F) {
    println!("{}", std::any::type_name::<T>());
}

fn main() {
    f(f::<usize, fn(usize)>);
}

You can do this with explicit trait bounds instead of impl Trait

fn test<F: Fn(F)>(f: F, g: F) {
    f(g);
}

Edit: now that I'm re-reading the question, do you want foo (or my test) to accept itself? My code express the type of a function that accepts itself, but it doesn't actually define one.

1 Like

This was supposedly disallowed by the issue I linked. So has it later been implemented and "unlocked" as a feature?

Edit: It's still disallowed if you try to make a closure and use it like that.

I, basically, want to be able to call foo(foo), and to be able to work inside foo with argument as with function.

fn foo<F:  Fn(F) >(f: F){
    f(f);
}
fn main() {
    foo(foo);
}

This does not compile: expected signature of fn(fn(_) {foo::<_>}) -> _

Indirectly:

fn foo(depth: usize, f: *const ()) {
    println!("{}", depth);
    let g: fn(usize, *const ()) = unsafe { std::mem::transmute(f) };
    g(depth + 1, f);
}

fn main() {
    foo(0, foo as *const fn(usize, *const()) as *const ());
}

Let me apply some of my Haskell knowledge here. In Haskell, a function definition such as

foo(f) = f(f)

will lead to errors like

   • Occurs check: cannot construct the infinite type: t ~ t -> t1
    • In the first argument of ‘f’, namely ‘(f)’
      In the expression: f (f)
      In an equation for ‘foo’: foo (f) = f (f)
    • Relevant bindings include
        f :: t -> t1 (bound at Recurse.hs:2:5)
        foo :: (t -> t1) -> t1 (bound at Recurse.hs:2:1)
  |
2 | foo(f) = f(f)
  |            ^

You can get a similar error in Rust with closures (using a closures because you don’t need explicit type annotations with closures):

fn bar() {
    |f: fn(_)| f(f);
}
error[E0308]: mismatched types
   --> src/main.rs:24:18
    |
 24 |     |f: fn(_)| f(f);
    |                  ^ cyclic type of infinite size

The argument type is infinite because it’s some type fn(T) -> () where T it the type of the function itself. I.e. T == fn(T) -> (), so

T == fn(T) -> () == fn(fn(T) -> ()) -> () == …

or without the -> ()s:

T == fn(T) == fn(fn(T)) == fn(fn(fn(T))) == fn(fn(fn(fn(T)))) == …

the name of the type needed here would get infinitely large. Type inference recognizes cycles like this in a check called “occurs check” (as mentioned in the Haskell error message; b.t.w. the t ~ t -> t1 in that error message is like T == fn(T) -> T1 in Rust syntax).

Note that “infinite” type doen’t mean that the type would need infinite memory, it’s a naming problem and the usual workaround for infinite types like this is to introduce a layer of abstraction via a newtype, e.g.

newtype Recur = Recur((Recur) -> ())
getRecur(Recur(f)) = f

foo(f) = getRecur(f)(f)

[The newtype syntax is similar to Rust’s enum syntax, e.g. enum Recur { Recur(fn(Recur) -> ()) }.]

This way we don’t have Recur == fn(Recur) -> (), but you can convert between the two, the getRecur function is for accessing the wrapped value.

So now, it then becomes possible to call the function on itself as long as you’re explicit about that extra newtype layer

bar() = foo(Recur(foo))

For anyone that knows Haskell, yes, I’m intentionally adding lots of unnecessary parantheses here to make it look more similar to the Rust translation.


Back to Rust, let’s try to translate this. Functions in Haskell are always dynamically dispatched (unless the compiler can optimizes it, which it does in most cases), so let’s use function pointers (like we already did in the example with the closure).

The newtype from Haskell becomes a struct in Rust:

#[derive(Copy, Clone)]
struct Recur(fn(Recur) -> ());
fn get_recur(Recur(f): Recur) -> (fn(Recur) -> ()) { f }

and now we can write foo

fn foo(f: Recur) { get_recur(f)(f) }

and call it

fn bar() { foo(Recur(foo)) }

Let’s make this syntactically just a little bit more ergonomic: To avoid the need for get_recur (or – more realistically – a field access like f.0(f)), you can implement Deref:

impl Deref for Recur {
    type Target = fn(Recur);

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

the final complete code can be found in this playground.

1 Like