Comment puis-je utiliser le système de type de Haskell pour faire respecter la justesse tout en étant en mesure de modèle match?

Question

Le mot Let que j'ai un HAA représentant une sorte de structure arborescente:

data Tree = ANode (Maybe Tree) (Maybe Tree) AValType
          | BNode (Maybe Tree) (Maybe Tree) BValType
          | CNode (Maybe Tree) (Maybe Tree) CValType

Pour autant que je sais qu'il n'y a aucun moyen de correspondance de motif contre les constructeurs de type (ou les fonctions correspondantes se serait pas un type?), Mais je voudrais encore utiliser le système de type compilation de temps pour éliminer la possibilité de retour ou l'analyse du mauvais « type » de nœud d'arbre. Par exemple, il se pourrait que la boîte de Nœuds-C soit que les parents à ANODES. Je pourrais avoir

parseANode :: Parser (Maybe Tree)

en fonction de l'analyse parsec que get est utilisé dans le cadre de mon analyseur Nœuds-C:

parseCNode :: Parser (Maybe Tree)
parseCNode = try (
                  string "<CNode>" >>
                  parseANode >>= \maybeanodel ->
                  parseANode >>= \maybeanoder ->
                  parseCValType >>= \cval ->
                  string "</CNode>"
                  return (Just (CNode maybeanodel maybeanoder cval))
             ) <|> return Nothing

Selon le système de type, parseANode pourrait finir par revenir un Maybe Nœuds-C, un Maybe bnode, ou peut-être Anode, mais je veux vraiment vous assurer qu'il ne retourne que Anode Peut-être. Notez que ce n'est pas un schéma-valeur des données ou de l'exécution vérification que je veux faire - je suis en fait juste essayer de vérifier la validité de l'analyseur que j'ai écrit pour un schéma d'arbre en particulier. OIEau, je ne cherche pas à vérifier les données pour schéma analysable correct, ce que je suis vraiment en train de faire est de vérifier mon analyseur pour l'exactitude du schéma - Je voudrais simplement vous assurer que je don « t botch-up parseANode un jour de retour autre chose qu'une valeur anode.

J'espérais que peut-être si je le constructeur en correspondance avec la valeur de la variable de liaison, que le type serait comprendre l'inférence ce que je voulais dire:

parseCNode :: Parser (Maybe Tree)
parseCNode = try (
                  string "<CNode>" >>
                  parseANode >>= \(Maybe (ANode left right avall)) ->
                  parseANode >>= \(Maybe (ANode left right avalr)) ->
                  parseCValType >>= \cval ->
                  string "</CNode>"
                  return (Just (CNode (Maybe (ANode left right avall)) (Maybe (ANode left right avalr)) cval))
             ) <|> return Nothing

Mais cela a beaucoup de problèmes, et non la moindre, que parseANode n'est plus libre de retourner rien. Et cela ne fonctionne pas de toute façon -. Il semble que cette variable de liaison est traité comme un match de modèle et le moteur d'exécution se plaint de motif non exhaustif correspondant lorsque parseANode soit ne renvoie rien ou bnode ou quelque chose peut-être

je pouvais faire quelque chose le long de ces lignes:

data ANode = ANode (Maybe BNode) (Maybe BNode) AValType
data BNode = BNode (Maybe CNode) (Maybe CNode) BValType
data CNode = CNode (Maybe ANode) (Maybe ANode) CValType

mais ce genre de suce, car il suppose que la contrainte est appliquée à tous les nœuds - je ne pourrais pas être intéressé à le faire - en fait, il pourrait juste être RCEOM qui ne peut être le rôle parental ANODES. Donc je suppose que je pourrais faire ceci:

data AnyNode = AnyANode ANode | AnyBNode BNode | AnyCNode CNode

data ANode = ANode (Maybe AnyNode) (Maybe AnyNode) AValType
data BNode = BNode (Maybe AnyNode) (Maybe AnyNode) BValType
data CNode = CNode (Maybe ANode) (Maybe ANode) CValType

mais cela rend beaucoup plus difficile à motif match contre son * Noeud - en fait, il est impossible parce qu'ils sont juste complètement types distincts. Je pourrais faire une classe de types où je voulais motif match, je suppose que

class Node t where
    matchingFunc :: t -> Bool

instance Node ANode where
    matchingFunc (ANode left right val) = testA val

instance Node BNode where
    matchingFunc (BNode left right val) = val == refBVal

instance Node CNode where
    matchingFunc (CNode left right val) = doSomethingWithACValAndReturnABool val

En tout cas, cela semble juste sorte de désordre. Quelqu'un peut-il penser à une façon plus succincte de le faire?

Answer 1

Je ne comprends pas votre objection à votre solution finale. Vous pouvez toujours match de modèle contre AnyNodes, comme ceci:

f (AnyANode (ANode x y z)) = ...

Il est un peu plus bavard, mais je pense qu'il a les propriétés techniques que vous voulez.

Answer 2

  

Je voudrais encore utiliser le système de type compilation de temps pour éliminer la possibilité de retourner ou de l'analyse du mauvais « type » de noeud Arbre

Cela sonne comme un cas d'utilisation pour GADTs.

{-# LANGUAGE GADTs, EmptyDataDecls #-}
data ATag
data BTag
data CTag

data Tree t where
  ANode :: Maybe (Tree t) -> Maybe (Tree t) -> AValType -> Tree ATag
  BNode :: Maybe (Tree t) -> Maybe (Tree t) -> BValType -> Tree BTag
  CNode :: Maybe (Tree t) -> Maybe (Tree t) -> CValType -> Tree CTag

Vous pouvez maintenant utiliser Tree t lorsque vous ne se soucient pas du type de noeud, ou Tree ATag quand vous faites.

Answer 3

Une extension de la réponse de keegan: coder les propriétés exactitude des arbres rouge / noir est en quelque sorte un exemple canonique. Ce fil a le code montrant à la fois la solution de type de données GADT et imbriquées: http: / /www.reddit.com/r/programming/comments/w1oz/how_are_gadts_useful_in_practical_programming/cw3i9