haskell - 使用递归方案的算法 W

Question

我希望能够使用定点数据类型和递归方案来制定hindley-milner 类型推理算法。忽略除实际递归部分之外的所有细节:

w env term = case term of 
    Lam n e -> lam (w (modify1 env) e)
    App a b -> app (w (modify2 env) a) (w (modify3 env) b)
    ...

该算法在递归遍历树直至到达叶子节点时构建环境数据结构 env。然后它会使用此信息再次构建结果。

如果没有env部分，这可以使用cata轻松实现。这(使用env)通常可以使用递归方案来完成吗？

Answer 1

Without the env part, this could be easily implemented with cata. Can this (with env) be done in general using recursion schemes?

您正在寻找的是 chronomorphism 。这允许您使用 future 和过去的两者结果进行递归。它并不像听起来那么用户友好，但它是使用递归方案执行操作的规范方式。