Higher-kinded generics in Java

Question

Suppose I have the following class:

public class FixExpr {
  Expr<FixExpr> in;
}

Now I want to introduce a generic argument, abstracting over the use of Expr:

public class Fix<F> {
  F<Fix<F>> in;
}

But Eclipse doesn't like this:

The type F is not generic; it cannot be parametrized with arguments <Fix<F>>

Is this possible at all or have I overlooked something that causes this specific instance to break?

Some background information: in Haskell this is a common way to write generic functions; I'm trying to port this to Java. The type argument F in the example above has kind * -> * instead of the usual kind *. In Haskell it looks like this:

newtype Fix f = In { out :: f (Fix f) }

Answer 1

I think what you're trying to do is simply not supported by Java generics. The simpler case of

public class Foo<T> {
    public T<String> bar() { return null; }
}

also does not compile using javac.

Since Java does not know at compile-time what T is, it can't guarantee that T<String> is at all meaningful. For example if you created a Foo<BufferedImage>, bar would have the signature

public BufferedImage<String> bar()

which is nonsensical. Since there is no mechanism to force you to only instantiate Foos with generic Ts, it refuses to compile.

Answer 2

Maybe you can try Scala, which is a functional language running on JVM, that supports higher-kinded generics.

---

[ EDIT by Rahul G ]

Here's how your particular example roughly translates to Scala:

trait Expr[+A]

trait FixExpr {
  val in: Expr[FixExpr]
}

trait Fix[F[_]] {
  val in: F[Fix[F]]
}

Answer 3

In order to pass a type parameter, the type definition has to declare that it accepts one (it has to be generic). Apparently, your F is not a generic type.

UPDATE: The line

F<Fix<F>> in;

declares a variable of type F which accepts a type parameter, the value of which is Fix, which itself accepts a type parameter, the value of which is F. F isn't even defined in your example. I think you may want

Fix<F> in;

That will give you a variable of type Fix (the type you did define in your example) to which you are passing a type parameter with value F. Since Fix is defined to accept a type parameter, this works.

UPDATE 2: Reread your title, and now I think you might be trying to do something similar to the approach presented in "Towards Equal Rights for Higher-Kinded Types" (PDF alert). If so, Java doesn't support that, but you might try Scala.

Answer 4

Still, there are ways to encode higer-kinded generics in Java. Please, have a look at higher-kinded-java project.

Using this as a library, you can modify your code like this:

public class Fix<F extends Type.Constructor> {
    Type.App<F, Fix<F>> in;
}

You should probably add an @GenerateTypeConstructor annotation to your Expr class

@GenerateTypeConstructor
public class Expr<S> {
    // ...
}

This annotation generates ExprTypeConstructor class. Now you can process your Fix of Expr like this:

class Main {
    void run() {
        runWithTyConstr(ExprTypeConstructor.get);
    }

    <E extends Type.Constructor> void runWithTyConstr(ExprTypeConstructor.Is<E> tyConstrKnowledge) {
        Expr<Fix<E>> one = Expr.lit(1);
        Expr<Fix<E>> two = Expr.lit(2);

        // convertToTypeApp method is generated by annotation processor
        Type.App<E, Fix<E>> oneAsTyApp = tyConstrKnowledge.convertToTypeApp(one);
        Type.App<E, Fix<E>> twoAsTyApp = tyConstrKnowledge.convertToTypeApp(two);

        Fix<E> oneFix = new Fix<>(oneAsTyApp);
        Fix<E> twoFix = new Fix<>(twoAsTyApp);

        Expr<Fix<E>> addition = Expr.add(oneFix, twoFix);
        process(addition, tyConstrKnowledge);
    }

    <E extends Type.Constructor> void process(
            Fix<E> fixedPoint,
            ExprTypeConstructor.Is<E> tyConstrKnowledge) {

        Type.App<E, Fix<E>> inTyApp = fixedPoint.getIn();

        // convertToExpr method is generated by annotation processor
        Expr<Fix<E>> in = tyConstrKnowledge.convertToExpr(inTyApp);

        for (Fix<E> subExpr: in.getSubExpressions()) {
            process(subExpr, tyConstrKnowledge);
        }
    }

}

Answer 5

There is a roundabout way to encode higher kinded types in Java as pointed out by Victor. The gist of it is to introduce a type H<F, T> to encode F<T>. This can then be used to encode fixed point of functors (i.e. Haskell's Fix type):

public interface Functor<F, T> {
    <R> H<F, R> map(Function<T, R> f);
}

public static record Fix<F extends H<F, T> & Functor<F, T>, T>(F f) {
    public Functor<F, Fix<F, T>> unfix() {
        return (Functor<F, Fix<F, T>>) f;
    }
}

From here you can go on and implement catamorphisms over initial algebras:

public interface Algebra<F, T> extends Function<H<F, T>, T> {}

public static <F extends H<F, T> & Functor<F, T>, T> Function<Fix<F, T>, T> cata(Algebra<F, T> alg) {
    return fix -> alg.apply(fix.unfix().map(cata(alg)));
}

See my GitHub repo for working code including some example algebras. (Note, IDE's like IntelliJ struggle with the code although it compiles and runs just fine with Java 15).

Answer 6

It looks as if you may want something like:

public class Fix<F extends Fix<F>> {
    private F in;
}

(See the Enum class, and questions about its generics.)