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）一般可以使用递归方案来完成吗？

score 3 · Accepted Answer

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

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

score 2 · Accepted Answer

是的，只需将目标设为cataa 函数Env -> a

– 卢基

是的，但您可能需要使用cata更高阶的运营商类型，计算可以修改环境并可能失败的操作。

– 养猪工

2 回答 2