How to implement fixed points of functors in Java

Question

I recently discovered how to simulate higher order types in Java in a somewhat roundabout way like so

interface H<F, T> { }

Here H encodes a higher order type that takes a type parameter F which itself takes parameter T.

Now this leaves me to wonder, can we use this to implement some more advanced constructs? E.g. fixed point of functors like Fix in Haskell and its corresponding catamorphisms?

Answer 1

Indeed this can be done by carefully translating the corresponding Haskell counterparts. Although this introduces a lot of line noise, the implementation is quite close to the original:

// Encoding of higher kinded type F of T
public interface H<F, T> { }

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

// newtype Fix f = Fix {unfix::f (Fix 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;
    }
}

// type Algebra f a = f a -> a
public interface Algebra<F, T> extends Function<H<F, T>, T> {}

 // cata :: Functor f => Algebra f a -> Fix f -> a
 // cata alg = alg . fmap (cata alg) . unfix
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)));
}

Amazingly this works and can be used to implement e.g. interpreters for expression algebras

// evalExprF :: Algebra ExprF Int
// evalExprF (Const n) = n
// evalExprF (Add m n) = m + n
// evalExprF (Mul m n) = m * n
public static class ExprAlg implements Algebra<Expr, Integer> {
    @Override
    public Integer apply(H<Expr, Integer> hExpr) {
        return Expr.expr(hExpr).match(
            conzt -> conzt.n,
            add   -> add.t1 + add.t2,
            mul   -> mul.t1 * mul.t2);
    }
}

Full working example in my GitHub repository.