Схемы рекурсии на Haskell: обозначьте дерево с промежуточными результатами

Question

С помощью cata Я могу сложить АСТ к результату. С Cofree Я могу хранить дополнительные аннотации на AST. Как я могу взять 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-алгебру.

затем

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

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