Recursive function type

Question

In Rob Pike's talk on lexical scanning in Go, he defines a function type stateFn which returns another stateFn, like so:

type stateFn func() stateFn

In an attempt to do something similar in Rust, I tried this:

type stateFn = fn() -> stateFn;

but the compiler complains "illegal recursive type; insert an enum or struct in the cycle, if this is desired".

Can I do this in Rust, and if so, how?

Answer 1

You can wrap the function type in a nominal type (i.e. a struct or enum). This is actually what the Go code is doing: type T U defines a new, distinct type T that's not directly interchangable with U, while Rust's type is just an alias, like type in Haskell and typedef in C.

So, one might write:

struct StateFn(fn() -> Option<StateFn>);

or

struct StateFn {
    f: fn() -> Option<StateFn>
}

(I've had to add the Option because Go's func can be nil, while Rust removes nullability by default, making it opt-in.)

That said, I suspect that func is a closure in Go (can store some internal state), while fn in Rust is just a function pointer (no state at all), so you may wish to use a closure in Rust too. One might do this by replacing fn() -> Option<StateFn> with a Box<Fn() -> Option<StateFn>>, and creating it with Box::new(move || { /* code here */ }).

One might also use FnMut instead of Fn which gives you more flexibility, or even FnOnce which represents a closure that can only be called once. Each of these places successively more restrictions on the caller, but gives the closure itself successively more flexibility. (However, "object safety" concerns mean that Box<FnOnce> doesn't work at the moment, "Purging proc" has more details and a work-around.)

struct StateFn {
    f: Box<FnMut() -> Option<StateFn>>
}

The parsing loop for any of these situations might look like:

let mut state_fn = Some(initial_fn);
while let Some(mut f) = state_fn {
    state_fn = (*f.f)()
}