Apologies for posting what seems like a Java topic here. Since the code is so unidiomatic and conceptually much closer to Haskell I thought I post it here.
After discovering how to encode higher kinded types in Java I set out to implement some stuff from the Data.Fix package. Notably fixed point of functors (Fix
) and catamorphisms (cata
):
// 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)));
}
Though there there is a lot of line noise, the implementations are actually pretty close to the Haskell counterparts.
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 code is in my GitHub repo.
I’d be interested to hear about improvements. E.g. how to further tighten the types as in some places I had to use raw types and casts although I’m quite sure that some casting is not avoidable.
Michael