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

Question

使用cataI 可以将 AST 折叠为结果。我可以在CofreeAST 上存储额外的注释。如何获取 AST 并在每个步骤中返回带注释的 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。我们在这里使用 type Cofree Term Result -> Result。它只是在根处返回注释。

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