Schémas de récurrence Haskell: Étiqueter l'arbre avec des résultats intermédiaires

En utilisant cata Je peux plier un AST pour un résultat. Avec Cofree je peux stocker des annotations supplémentaires sur l'AST. Comment est-ce que je peux prendre un AST et renvoyer un AST annoté avec les résultats à chaque étape du chemin?Schémas de récurrence Haskell: Étiqueter l'arbre avec des résultats intermédiaires

alg :: Term Result -> Result 
alg = undefined 

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

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

Source

2017-09-09 user47376

double possible de https://stackoverflow.com/questions/38462563/how-to-work-with-ast-with-cofree-annotation –

(tl; dr: utiliser 'produit ', pas' Cofree', pour l'étiquetage.) –

Lorsque vous utilisez 'Product', il va itérer sur les deux structures simoultaniasly, correct? – user47376

Est-ce que cette algèbre modifiée fonctionne?

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 est de Control.Comonad. Nous l'utilisons ici avec le type Cofree Term Result -> Result. Il renvoie simplement l'annotation à la racine. Nous permet de réutiliser notre définition alg précédente.

Source

2017-09-09 15:41:06 danidiaz

Merci! Mais il y a un autre problème: en fait mon 'Result' est enveloppé dans une monade. Donc 'run ':: Fix Term -> Cofree Term (m Résultat)'. Que puis-je faire pour obtenir 'm (Cofree Term Result)'? – user47376

@ user47376 Votre algèbre d'origine est-elle semblable à 'alg :: Term (m Result) -> m Result'? – danidiaz

Oui. Le type complet est 'hm :: (MonadError TypeError m, MonadState Count m) => Term (Alias m) -> Alias m'. Où 'type alias m = environnement -> m (Substitution, type)'. Donc, il est enveloppé dans toutes sortes de choses. Je suis seulement intéressé par 'Type'. Donc, le résultat final devrait être 'Cofree Term Type' – user47376

Si vous avez juste besoin d'un simple catamorphisme, vous pouvez utiliser une fonction comme cataM. Cela vous permet de replier les valeurs monadiques de sorte que les actions soient correctement ordonnées. De plus, vous n'avez pas besoin d'écrire un passe-partout pour envelopper votre algèbre F.

Puis

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

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

Source

2017-09-09 17:29:11

Schémas de récurrence Haskell: Étiqueter l'arbre avec des résultats intermédiaires

Répondre

Questions connexes