How to break cyclic reference in function traits?

#1

How do I convert the following unacceptable (“unsupported cyclic reference between types/traits detected”) Rust to something that works?

type Generator<A> = Fn(Consumer<A>) -> bool;
type Consumer<A> = Fn(A, bool, Generator<A>) -> bool;

I want to define closures of these generator and consumer types.

I’m trying to translate this from Haskell but am not sure how to. Here’s the Haskell, where circularity is broken through newtype. I realize that there are constraints in Rust because of the nature of closures as actually different-sized structs with explicit environment captures synthesized by the compiler to implement the function traits, but breaking the circularity is stumping me somehow.

newtype Generator a = G { runG :: Consumer a -> Bool }
newtype Consumer a  = C { runC :: a -> Bool -> Generator a -> Bool }
#2

One way is to wrap them in a struct (which is semantically the same as the Haskell version):

struct Generator<A>(Fn(Consumer<A>) -> bool);
struct Consumer<A>(Fn(A, bool, Generator<A>) -> bool);

although those signatures aren’t actually usable due to the unsized types involved. These might be:

struct Generator<'a, A>(&'a Fn(&Consumer<A>) -> bool);
struct Consumer<'a, A>(&'a Fn(A, bool, &Generator<A>) -> bool);

There’s currently no guaranteed tail recursion, though, so implementing such functions is probably a bad idea.

#3

Thanks, the structs you gave seem exactly what I need.

No, there’s not going to be tail recursion, but that’s OK, because the point is going to be to show stack-allocated continuations with known depth.

#4

Rust type is not the same as Haskell newtype. Rust’s type is a type alias. So if I do type Foo<T> = Vec<T> Foo<T> is no different from a vector. An object of type Foo is an object of type Vec

Like @comex mentioned you need to wrap them in a struct. struct Foo(Bar) is called a newtype in Rust, and behaves like the Haskell newtypes – it’s a new type which just contains the old one. You can convert between the new and old types easily, but the new type is a blank slate.

#5

Yes, I’ve been using the struct Rust newtype mechanism extensively in all my Rust code for over a year now (see my presentation https://github.com/FranklinChen/type-directed-tdd-rust). The key in the situation here was in adding the lifetimes and all the references in order not to end up with infinitely sized types.