haskell syntax




Correspondance de motifs-Prolog vs. Haskell (4)

Ce n'est pas une question de devoirs, plutôt une question de guide d'étude d'examen. Quelle est la différence entre l'appariement de modèles dans Prolog Vs Haskell?

J'ai fait quelques recherches et lire sur les théories derrière eux ne me donne pas vraiment une compréhension solide entre les deux. J'ai lu que dans Prolog, l'appariement de formes est différent parce qu'il a la capacité d'unifier des variables et donc d'être capable de déduire à travers la résolution et cracher la réponse possible

eg ?- [a,b] = [a,X]
   X = b

Maintenant, je ne suis pas sûr de savoir comment afficher le motif dans Haskell. Je sais que la même requête ci-dessus montrée dans Prolog ne fonctionnera pas dans Haskell parce que Haskell ne peut pas unifier comme Prolog. Je me rappelle quelque part que pour avoir la même réponse dans Haskell, il faut le dire explicitement à travers les gardes.

Je sais que je suis assez proche de la comprendre, mais j'ai besoin de quelqu'un pour décomposer le style Barney pour moi afin que je puisse comprendre complètement et expliquer à un enfant de 12 ans. Cela me dérange depuis un certain temps et je n'arrive pas à trouver une explication solide.

En passant, l'exemple ci-dessus était juste pour vous montrer ce que j'ai appris jusqu'à présent et que j'essaie de trouver une réponse. Ma question principale ne concerne pas les exemples ci-dessus mais plutôt une compréhension complète de la différence entre les deux.


En ajoutant à la réponse de LeleDumbo, nous pourrions dire que l'unification Prolog construit des termes aussi bien que les déconstruit , tandis que dans Haskell la phase de construction est commodément demandée pour la valeur retournée.

Bien sûr, une telle caractéristique est ce qui permet de créer des prédicats «bidirectionnels» purs, exploités par exemple dans les DCG, qui, avec certaines restrictions, peuvent être utilisés à la fois pour l'analyse et la génération.


La correspondance de modèle Prolog est basée sur l'unification, en particulier l' algorithme Martelli-Montanari (moins la vérification des occurrences, par défaut). Cet algorithme correspond à des valeurs de la même position, en liant les variables d'un côté à une valeur de la position correspondante de l'autre côté. Ce type de correspondance de modèle peut fonctionner dans les deux sens. Par conséquent, dans Prolog, vous pouvez utiliser des arguments en entrée et en sortie. Un exemple simple, la length/2 prédicat. Nous pourrions l'utiliser pour (commentaire explique la requête):

?- length([],0).      % is the length of empty list zero?
?- length([a,b,c],X). % what's the length of list consisting of a,b and c?
?- length(L,5).       % give me all lists that have length of 5

La correspondance de modèle Haskell est une correspondance unidirectionnelle, pour lier des variables à différentes parties d'une valeur donnée. Une fois lié, il effectue l'action correspondante (le côté droit). Par exemple, dans un appel de fonction, la correspondance de modèle peut décider quelle fonction appeler. par exemple:

sum []     = 0
sum (x:xs) = x + sum xs

la première somme lie la liste vide, tandis que la seconde lie une liste d'au moins 1 élément. Sur la base de ceci, étant donné la sum <a list> , le résultat peut être soit 0 soit x + sum xs selon que sum <a list> correspond à sum [] ou sum (x:xs) .


La différence entre l'appariement de motifs comme dans Haskell et l'unification de Prolog provient du rôle fondamentalement différent des variables dans les deux langues.

Dans Haskell, les variables contiennent des valeurs. Valeurs concrètes Une telle valeur n'a peut-être pas encore été calculée, et elle pourrait même être ⊥, mais sinon, c'est une valeur concrète. Dans Haskell, vous ne pouvez pas prendre une variable et indiquer seulement certaines propriétés de sa valeur en premier.

La correspondance de modèle signifie donc qu'une valeur concrète est comparée à un modèle qui contient certaines variables. Le résultat d'un tel appariement est soit un échec, soit une liaison des variables à des valeurs concrètes. Dans Haskell, ceci est encore restreint pour éviter la nécessité d'une comparaison générale, ce qui impliquerait que la classe Eq est définie pour les termes correspondants.

En Prolog, cependant, les variables peuvent se référer à un ensemble de solutions possibles. Les variables peuvent apparaître n'importe où - également quelque part entre les autres valeurs. L'unification garantit désormais que les égalités indiquées sont toujours valables et que le résultat est représenté de façon optimale, c'est-à-dire que l'unificateur le plus général est calculé.


| ?- length(L,5).                      
L = [_,_,_,_,_]
| ?- length(L,5), maplist(=(E),L).
L = [E,E,E,E,E]

Donc Prolog ne répond pas ici avec des valeurs concrètes comme L = [1,1,1,1,1] ou L = [[],[],[],[],[]] mais donne l'unificateur le plus général en tant que réponse qui contient toutes ces valeurs concrètes.


Personne n'a mentionné la différence très importante suivante. La correspondance de modèle dans Prolog est essayée pour chaque clause d'un prédicat, même si l'une des correspondances précédentes a réussi (sauf si elle est interrompue par une coupure ). Mais dans le modèle de Haskell, l'appariement sur les clauses est tenté seulement jusqu'au premier succès . Aucune autre alternative n'est essayée (sauf si le match a été rejeté par un gardien ).

La correspondance de modèle de Prolog établit une contrainte d'égalité au sens le plus général (voir la réponse de @false pour plus de détails). Le partage est explicite : A=B, A=5 met B=5 aussi bien. Ceci est possible parce que le logvar de Prolog peut être dans un état pas encore établi (c'est-à-dire non instancié ). Cela facilite l' attacher un nœud (une technique de programmation de base en fait, à savoir des listes de différences ).

Dans Haskell, toute variable ne peut être définie qu'une seule fois au niveau de la syntaxe . En Prolog, un logvar n'est défini qu'une seule fois (sans backtracking ), mais il est autorisé à pointer vers une structure incomplète (data), où les trous sont représentés par d'autres logvars non encore instanciés qui peuvent être définis à un moment ultérieur .

Dans Haskell, une structure donnée définie avec une récursion gardée est progressivement étoffée comme l'exige l'accès. En Prolog, après l'instanciation initiale d'une variable, toute unification ultérieure est transformée en vérification de la compatibilité des termes et éventuellement en une instanciation ultérieure (peut-être partielle encore une fois) ("remplir" les trous explicitement ).





pattern-matching