Dans Haskell, son simple pour créer un type de données pour un arbre récursif, comme ce que nous avons avec des documents XML:Comment puis-je modéliser une structure de données arborescente avec des restrictions sur l'emplacement de chaque type de nœud?
data XML =
Text String -- Text of text node
| Elem String [XML] -- Tagname; Child nodes
et ses plis connexes:
-- Simple fold (Child trees don't see the surrounding context.)
foldt :: (String -> a) -> (String -> [a] -> a) -> XML -> a
foldt fT fE (Text text) = fT text
foldt fT fE (Elem tagname ts) = fE tagname (map (foldt fT fE) ts)
-- Threaded fold for streaming applications.
-- See http://okmij.org/ftp/papers/XML-parsing.ps.gz
foldts :: (a -> String -> a) -> (a -> String -> a) -> (a -> a -> String -> a) -> a -> XML -> a
foldts fT fE_begin fE_end = go
where
go seed (Text text) = fT seed text
go seed (Elem tag children) =
let seed' = fE_begin seed tag in
let seed'' = foldl go seed' children in
fE_end seed seed'' tag
Mon problème est maintenant que je Je ne sais pas comment ajouter des restrictions supplémentaires à mon type de données Tree afin de modéliser HTML. En HTML, chaque élément ne peut apparaître que dans le bon contexts et chaque élément correspond à un contexte différent pour ses enfants. Par exemple:
- Les éléments vides tels que img ont un modèle de contexte vide et ne doivent pas avoir d'enfants.
- éléments avec un modèle de contenu de texte, tels que title, peuvent seulement avoir des nœuds de texte que les enfants (pas de balises imbriquées autorisées)
- div éléments ne peuvent pas apparaître dans un contexte de Phrasing et par conséquent ne sont pas autorisés à être des descendants de span éléments.
Mes questions sont les suivantes:
qu'aurais-je faire pour modéliser ces restrictions haskell98? (Je demande cela parce que je suppose que le modèle Haskell98 devrait mieux traduire vers d'autres langages de programmation)
J'imagine que nous pourrions avoir à créer beaucoup de différents types de données pour les différents contextes, mais je ne sais pas comment le faire dans un principe et de manière claire. Comment puis-je faire cela sans me perdre et à quoi ressembleront les fonctions de pli? A quoi ressemblerait le modèle si nous pouvions utiliser des fonctionnalités GHC modernes telles que les GADT?
je un GADTs de Hunch pourraient aider à pousser les restrictions dans le typechecker, en gardant les fonctions de pliage simple mais je suis ne pas beaucoup d'expérience avec eux ...
Je ne ai pas besoin une solution fonctionnant à 100%, puisque cela dépasserait évidemment le cadre d'une discussion Stack Overflow. J'ai juste besoin de suffisamment pour être capable d'avoir une meilleure compréhension des GADTs et des choses comme et pouvoir faire le reste par moi-même.
Je pense que le modèle de constructeur intelligent est applicable .. mais ce que vous voulez vraiment ici ressemble un peu à un typage dépendant. http://www.haskell.org/haskellwiki/Smart_constructors – jozefg
@jozefg: L'approche du constructeur intelligent aide (et est ce que j'utilise en ce moment) mais j'ai trouvé que ça contraignait comment vous êtes autorisé à construire des choses et ça ne joue pas très bien avec un streaming, API similaire à SAX. D'un autre côté, si j'ai un modèle entièrement sécurisé, je peux concevoir une version de streaming robuste basée sur la fonction de pliage correspondante. – hugomg
@jozefg: En ce qui concerne les types dépendants, je ne pense pas que nous ayons besoin d'aller aussi loin si nous supposons que les noms d'éléments autorisés proviennent d'un ensemble fini. (Bien sûr, les choses peuvent devenir moche mais c'est le but de l'exercice) – hugomg