算法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.这个(with env)一般可以使用递归方案吗？

Answer 1

\n

cata是的，只需将a 函数作为目标即可Env -> a

\n

\n\n

\xe2\x80\x93 卢基

\n\n

\n

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

\n

\n\n

\xe2\x80\x93 猪工

\n