Haskell递归方案:标记具有中间结果的树

Question

使用cata我可以将AST折叠到结果。使用Cofree，我可以在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。我们在此处使用Cofree Term Result -> Result类型。它只是返回根部的注释。

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

Answer 2

如果您只需要简单的血统，则可以使用cataM之类的函数。这使您可以折叠单声道值，从而正确订购了操作。另外，您无需写任何样板即可包装F-Algebra。

然后

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