如何在 Java 中实现函子的不动点

Question

我最近发现了如何 simulate higher order types in Java 像这样

interface H<F, T> { }

这里 H 编码一个高阶类型，它接受一个类型参数 F，它本身接受参数 T.

现在这让我想知道，我们可以用它来实现一些更高级的构造吗？例如。函子不动点喜欢 Fix in Haskell and its corresponding catamorphisms?

Answer 1

确实，这可以通过仔细翻译相应的 Haskell 对应项来完成。虽然这引入了很多线路噪声，实现与原始版本非常接近：

// 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)));
}

令人惊奇的是，它的工作原理可以用来实现例如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);
    }
}

我的 GitHub repository 中的完整工作示例。

如何在 Java 中实现函子的不动点

How to implement fixed points of functors in Java

java

functor

higher-kinded-types

catamorphism

fixed-point-iteration