Recursion, corecursion and thunks

Java does not support tail calls.

The usual workaround is a type like the following.

class Thunk<A> {
     boolean isDone();
     Thunk step();
     A finish();
}

Looked at mathematically this type is really a corecursive definition sort of like a stream datatype.

exists b. (b -> (b + a))

It happens there exists a dual recursive datatype.

forall b. ((a -> b) -> (b -> b) -> b

You can apply the math to a simple factorial function like so.

 <C> C fact (int m, int n, Function<Supplier<C>,C> y, Function<Integer, C> result) {
     if (n < 1){
          return h.apply(m);
     }
     return y.apply(() -> fact(m *n, n -1, y, h));
}

At first it appears we have gained nothing from this approach except a degree of indirection. But in fact this lets us delay and thunk an evaluation step or just evaluate it directly.

I’m still not sure this is the best approach for tail calls on the JVM but I remain hopeful recursion schemes will bring a better answer than the ordinary one.

原文链接：Recursion, corecursion and thunks