Haskell 递归方案：用中间结果标记树

Question

使用 cata 我可以将 AST 折叠成一个结果。使用 Cofree 我可以在 AST 上存储额外的注释。如何获取 AST 和 return 带注释的 AST 以及每一步的结果？

alg :: Term Result -> Result
alg = undefined

run :: Fix Term -> Result
run ast = cata alg ast

run' :: Fix Term -> Cofree Term Result
run' = ???

Answer 1

这个修改后的代数有用吗？

alg' :: Term (Cofree Term Result) -> Cofree Term Result
alg' t = alg (fmap extract t) :< t  

run' :: Fix Term -> Cofree Term Result
run' ast = cata alg' ast

extract 来自 Control.Comonad。我们在这里使用类型 Cofree Term Result -> Result。它只是 returns 根部的注释。

fmap extract :: Term (Cofree Term Result) -> Term Result 让我们重用之前的 alg 定义。

Answer 2

如果你只需要一个简单的变形，你可以使用像 cataM 这样的函数。这允许您折叠 monadic 值，以便正确排序操作。另外，您不需要编写任何样板来包装您的 F 代数。

然后

alg :: Term Result -> Cofree Term Result
alg = undefined

run' :: Fix Term -> Cofree Term Result
run' = cataM alg

Haskell 递归方案：用中间结果标记树

Haskell Recursion Schemes: Label the tree with intermediate results

haskell

recursion

recursive-datastructures

recursion-schemes

corecursion