La suppression de toutes les occurrences d'un élément dans une liste

Essaie d'écrire une procédure qui donne une valeur et une liste, il supprime toutes les occurrences de la valeur dans la liste a écrit:

delMember(X, [], []) :- !.
delMember(X, [X|Xs], Y) :- !, delMember(X, Xs, Y).
delMember(X, [T|Xs], Y) :- !, delMember(X, Xs, Y2), append([T], Y2, Y).

Depuis le cut ce code ne peut pas répondre correctement les requêtes comme:

delMember(Y, [1,2,3,1,2,3,1,2,3], [1, 2, 1, 2, 1, 2 ]).

Si je supprime les coupes:

delMember(X, [], []).
delMember(X, [X|Xs], Y) :- delMember(X, Xs, Y).
delMember(X, [T|Xs], Y) :- delMember(X, Xs, Y2), append([T], Y2, Y).

d'échec des requêtes comme:

delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,3,1,2,3,1,2,3]).

(renvoie true , lorsque la réponse correcte est false).

Comment puis-je faire cela fonctionne dans les deux situations?

Je peux peut-être vérifier que X is not T dans la troisième ligne de code, j'ai essayé:

delMember(X, [T|Xs], Y) :- not(X = T), delMember(X, Xs, Y2), append([T], Y2, Y).

mais il ne fonctionne pas.

InformationsquelleAutor Aslan986 | 2012-08-29

prolog prolog-dif

7

Utilisation de la coupe
```
delMember(X, [], []) :- !.
delMember(X, [X|Xs], Y) :- !, delMember(X, Xs, Y).
delMember(X, [T|Xs], Y) :- !, delMember(X, Xs, Y2), append([T], Y2, Y).
```
Ici, vous pouvez voir que vous utilisez !/0 dans le dernier alinéa de votre prédicat. Il n'est pas nécessaire. Après le dernier alinéa, il n'y a pas d'autre choix à gauche (Prolog se souvient des points de choix, de gauche à droite et de haut en bas), donc une coupe (qui supprime choix), de ne pas faire quelque chose d'utile, puisque vous êtes déjà au bas de votre liste de choix.

Pour illustrer, voir
```
a :- b; c.
a :- d.
```
Ici, pour prouver a, Prolog va d'abord essayer b, puis c, puis d (de gauche à droite, puis de haut en bas).

BTW, en tant que débutant dans le Prologue, vous devez aller jusqu'à totalement éviter l'utilisation de la coupe. Ce sera juste ajouter à vos incompréhensions, tant que vous n'obtenez pas la récursivité et les autres bases de la logique de programmation.

Prologue de la récursivité

Cette petite note de côté, votre problème est que vous n'avez pas bien compris Prologue de la récursivité encore. Veuillez consulter la première partie de cette réponse que déjà les adresses de cette préoccupation.

Votre troisième article est faux:
```
delMember(X, [T|Xs], Y) :- delMember(X, Xs, Y2), append([T], Y2, Y).
```
il faut lire:
```
delMember(X, [T|Xs], [T|Y]) :- delMember(X, Xs, Y).
```
Bien, ce n'est pas vraiment mauvais, c'est juste vraiment à désirer. Ce n'est pas récursives terminales et utilise append/3, qui serait à son tour votre linéaire de prédicat dans une quadratique. De Plus, comme vous l'avez remarqué, puisqu'il n'est pas récursives terminales, la résiliation est plus difficile à obtenir dans certains cas.

Ensuite, pour supprimer l'utilisation de la coupe !/0, vous pouvez envisager d'ajouter un garde à la dernière clause:
```
delMember(_, [], []).
delMember(X, [X|Xs], Y) :-
    delMember(X, Xs, Y).
delMember(X, [T|Xs], [T|Y]) :-
    dif(X, T),
    delMember(X, Xs, Y).
```
La garde, dif(X, T), précise que, si nous sommes dans le troisième cas, nous ne pouvons pas être dans la deuxième dans le même temps : X ne peut être unifiée avec T ici.

Remarque, il y a toujours une façon on ne peut pas utiliser le prédicat, c'est, +, -, +, comme cTI nous le dit. De sorte que des requêtes comme ?- delMember(1, R, [2, 3]). en boucle avec ma version.

J'espère que ça a été utile.
- Merci, j'ai juste une question. Si j'ai une requête delMember(Y, [1,2,3,1,2,3], X), j'obtiens seulement une solution (Y=1, X=[2,3,2,3]). Pourquoi je ne suis pas aussi Y=2 et Y=3 ?
- C'est parce que nous utilisons (\=)/2, qui n'a pas vraiment d'adapter le travail. Que les résultats de Prolog seulement être en mesure d'utiliser la deuxième clause de trouver X. Essayez d'utiliser dif(X, T) au lieu de X \= T
- Grande pêche! dif/2 c'est vraiment une drôle de bête, et ce en faire bon usage.
- Yup, encore +, -, + boucles. Pas la meilleure solution!
InformationsquelleAutor m09
4

Ce n'est pas une vraie réponse, juste une longue note à Mog et thanosQR réponses, trop long pour tenir dans un commentaire.
De telles réponses sont agréables et instructifs, mais la coupe de suppression doivent être rethinked. Considérer:
```
delMember(_, [], []).
delMember(X, [X|Xs], Y) :-
    delMember(X, Xs, Y), !.
delMember(X, [T|Xs], [T|Y]) :-
    delMember(X, Xs, Y).
```
Cette définition permet
```
?- delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,1,2,1,2]).
Y = 3.
```
qui échoue dans l'original Mog' code à cause de la garde en dernière cause. Il vaut la peine de noter que le remplacement de il la garde avec X \== T (qui limite le test apparié de l'instanciation de l'état), également de résoudre cette question, comme l'a noté thanosQR.

Mais aucun de ces fragments de résoudre le cas général:
```
?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
X = 1,
Y = [1, 2] ;
Y = [1, 2, 1].
```
- J'ai pris del/3 verbatim de votre réponse. La sortie produite semble erroné ; X = 1, Y = [1, 2] ;
- ah oui, je l'ai maintenant! (a l'impression que la sortie que vous avez posté est ce que la solution était censé avoir). en effet, comme l', \==/2 ne marche pas en fait à imposer une restriction sur X, il peut être plus tard unifié avec 1. Je pense que cela peut être résolu en inversant les règles dans le corps (del(X, [H|L1], [H|L2]):- del(X,L1,L2), X\==H.)
- oui, ça fonctionne! Nice et la solution la plus simple.
- merci 🙂 édité mon post et ajouté une queue-une version récursive (j'espère qu'il na pas changer la sémantique).
- même si pas de queue récursive, c'est déjà plus rapide que le dif/2 version:?- time(forall((between(1,30,N),length(X,N),delMember(1,X,[2,3,2,3])),true)). % 2,557,034 inferences, 1,002 CPU in 1,003 seconds (100% CPU, 2551178 Lips) true. ?- time(forall((between(1,30,N),length(X,N),del2(1,X,[2,3,2,3])),true)). % 1,319,018 inferences, 0,671 CPU in 0,672 seconds (100% CPU, 1965375 Lips). del2 c'est votre version, delMember utilisation dif/2
- en effet, elle aussi, la queue une version récursive est en fait (un peu) plus lent: ?- time(forall((between(1,30,N),length(X,N),del0(1,X,[2,3,2,3])),true)). % 1,318,958 inferences, 0.292 CPU in 0.297 seconds (98% CPU, 4511074 Lips) time(forall((between(1,30,N),length(X,N),del_tr(1,X,[2,3,2,3])),true)). % 1,318,957 inferences, 0.307 CPU in 0.307 seconds (100% CPU, 4292830 Lips)
InformationsquelleAutor CapelliC
3

Permet de faire un peu de reformuler: puisque vous souhaitez utiliser le prédicat dans plus d'une instanciation du modèle "une procédure qui donne une valeur et une liste, il supprime toutes les occurrence de cette valeur dans la liste" ne définit pas comment il doit se comporter dans les autres cas. Donc, nous voulons probablement quelque chose comme "le prédicat est vrai si le deuxième et le troisième argument est la liste L1, L2 et L1 est la même liste avec L2, si on ignore toutes les occurrences de la première argument"

Maintenant, il y a deux façons d'écrire un prédicat avec plusieurs instanciations; vous pouvez utiliser les méta-logique des prédicats tels que var/1 et ground/1 et l'écriture de code pour chacun (ce qui va probablement vous permettre d'écrire du code optimisé pour l'instanciation) ou écrire du code qui permettrait de définir les propriétés logiquement (qui peut être plus difficile).

Dans ce cas, on pourrait faire quelque chose comme ça:
```
    del(_, [], []).
    del(X, [X|L1], L2):-
        del(X,L1,L2).
    del(X, [H|L1], [H|L2]):-
        X\==H,
        del(X,L1,L2).
```
qui a le comportement suivant:
```
19 ?- del(1, [1,2,3], X).
X = [2, 3] ;
false.
1,2,3,
20 ?- del(1, [1,2,3], [2,3]).
true ;
false.

21 ?- del(X, [1,2,3], [2,3]).
X = 1 ;
false.

22 ?- del(X, [1,2,3], Y).
X = 1,
Y = [2, 3] ;
X = 2,
Y = [1, 3] ;
X = 3,
Y = [1, 2] ;
Y = [1, 2, 3] ;
false.

23 ?- del(X, P, Y).
P = Y, Y = [] ;
P = [X],
Y = [] ;
P = [X, X],
Y = [] ;
P = [X, X, X],
Y = [] ;
P = [X, X, X, X],
Y = [] ;
P = [X, X, X, X, X],
Y = [] ;
P = [X, X, X, X, X, X],
Y = [] .
```
concernant le dernier appel; prologue renvoie une liste de X qui pousse cause profondeur d'abord de l'algorithme est utilisé; en utilisant length/2 nous pouvons obtenir les résultats en largeur d'abord (_G signifie que la variable n'est pas instancié (il peut être n'importe quoi)):
```
24 ?- length(P,N), del(X, P, Y).
P = [],
N = 0,
Y = [] ;
P = [X],
N = 1,
Y = [] ;
P = [_G548],
N = 1,
Y = [_G548] ;
P = [X, X],
N = 2,
Y = [] ;
P = [X, _G551],
N = 2,
Y = [_G551] ;
P = [_G548, X],
N = 2,
Y = [_G548] ;
P = [_G548, _G551],
N = 2,
Y = [_G548, _G551] ;
P = [X, X, X],
```
edit: comme @chac souligné, le prédicat ci-dessus se comporte de manière incorrecte si la première liste a (au moins) un double élément:
```
?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
X = 1,
Y = [1, 2] ;                  <----- wrong
Y = [1, 2, 1].
```
c'est parce que \==/2 et \=/2 pas en fait à imposer une restriction sur la variable.
ceci peut être résolu en changeant l'ordre des règles dans le troisième alinéa:
```
    del(_, [], []).
    del(X, [X|L1], L2):-
        del(X,L1,L2).
    del(X, [H|L1], [H|L2]):-
        del(X,L1,L2),
        X\==H.


4 ?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
Y = [1, 2, 1] ;
false.
```
toutefois, cela signifie que le prédicat n'est plus la queue-récursive. pour corriger que nous avons pu maintenir une liste des valeurs de X ne devrait pas être:
```
del(X,L1,L2):-
    del(X,L1,L2,[]).

del(X, [], [], NotX):-
    \+ member(X,NotX).
del(X, [X|L1], L2, NotX):-
    del(X,L1,L2,NotX).
del(X, [H|L1], [H|L2], NotX):-
    X\==H,     % <--- optional; stops the execution earlier (saving time)
    del(X,L1,L2,[H|NotX]).
```
toutefois, conformément à la suivante, la queue une version récursive est en fait plus lentement:
```
?-time(forall((between(1,50,N),length(X,N),del2(1,X,[2,3,2,3])),true)).
% 25,600,793 inferences, 5.468 CPU in 5.548 seconds (99% CPU, 4682134 Lips)
true.

?- time(forall((between(1,50,N),length(X,N),del_tr(1,X,[2,3,2,3])),true)).
% 37,346,143 inferences, 6.426 CPU in 6.428 seconds (100% CPU, 5811563 Lips)
true.
```
encore, l' + - + ne fonctionne pas (elle tombe dans une boucle infinie). mais pourquoi? le problème se situe dans l'ordre des clauses:
del(1, L1, [2]) va d'abord appliquer la règle qui "ajoute" X à la tête de la L1, puis applique la même règle à tout jamais.
cela peut être contré par l'aide (encore une fois) length/2:
```
?- length(X,2), del(1,X,[2]).
X = [1, 2] ;
X = [2, 1] ;
false.
```
sinon, nous pouvons changer l'ordre des clauses:
```
del(_, [], []).
del(X, [H|L1], [H|L2]):-
    X\==H,
    del(X,L1,L2),
    X\==H.
del(X, [X|L1], L2):-
    del(X,L1,L2).
```
encore length/2 pourrait être de nouveau utile car, sans lui, prolog fait un parcours en profondeur d'abord de recherche:
```
?- del(1,X,[2]).
X = [2] ;
X = [2, 1] ;
X = [2, 1, 1] ;
X = [2, 1, 1, 1] ;
X = [2, 1, 1, 1, 1] ;
X = [2, 1, 1, 1, 1, 1] ;
X = [2, 1, 1, 1, 1, 1, 1] 
```
bien sûr length/2 peuvent être intégrées dans une enveloppe prédicat car elle n'affecte pas les autres de l'instanciation de modèles.

InformationsquelleAutor Thanos Tintinidis
0

Voici un extrait de code qui fonctionne aussi avec le premier et troisième arguments uninstantiated:
```
delMember(X, Y, Z):-
  bagof(A, (setof(X, member(X, Y), L), member(X, L), member(A, Y), A\==X), Z).
```
Je vais vous expliquer ici ce que ce code ne. L'idée est de:
1. Construire une liste de membres distincts de la liste d'entrée Y, qui unifier avec la participation des membres X
2. Alors pour chaque X de la liste construite sur 1) jeter cet élément de la liste d'entrée pour obtenir la liste de sortie Z sans membre X.
L'étape 1 est réalisée avec setof(X, member(X, Y), L) et il fonctionne de deux manières. Si le paramètre X est déjà instancié puis L sera soit la liste [X] si X est contenue dans le paramètre d'entrée Y, de il échouera si X n'est pas contenue dans Y. D'autre part, si X était uninstantiated puis L sera l'ensemble des éléments distincts de paramètre d'entrée Y.

Maintenant à l'étape 2 nous revenir en arrière sur chaque élément de L, et pour chaque membre de cette liste, nous filtre de cet élément de la liste d'entrée Y ce qui donne le résultat. Nous recueillons tous ces éléments dans la liste de sortie Z.

Noter que si le paramètre X est uninstantiated lors de la procédure de wass a appelé, lors de la mandature de member(X, Y) nous permettra d'obtenir tous les membres de la liste d'entrée Y qui sera utilisé pour le filtrage.

Cas de Test:
```
?- delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,3,1,2,3,1,2,3]).
false.

?- delMember(Y, [1,2,3,1,2,3], X).
Y = 1,
X = [2, 3, 2, 3] ;
Y = 2,
X = [1, 3, 1, 3] ;
Y = 3,
X = [1, 2, 1, 2].

?- delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,1,2,1,2]).
Y = 3.

?- delMember(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1].
```
- Je pense que cette réponse favorise vraiment les mauvaises pratiques, en particulier dans un poste adressée à un débutant.
- je ne sais pas pourquoi vous l'avez dit... peut-être parce que je n'ai pas d'expliquer le code ? Cette application n'utilise pas vraiment les méchants fonction de Prologue...
- btw, ?- delMember(S, [1, 2], R). S = 1, R = [2] ; S = 2, R = [1]. ne donne pas la bonne réponse R = [1, 2], dif(S, 1), dif(S, 2). Voir mon edit.
- La dernière réponse que vous avez fournie (R = [1, 2], dif(X, 1), dif(X, 2)) est erroné selon OPs question. OP dit que delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,3,1,2,3,1,2,3]). doit échouer.
- Bien OP dit true n'est pas correcte, peut-être parce qu'il n'a pas de sens liaisons. Solutions correctes faire. Naturelles et de la sémantique de del comme spécifié dans le reste de l'OP, du point de vue de cet être vrai avec les liaisons corrects.
InformationsquelleAutor gusbro

Vous devez vous connecter pour publier un commentaire.

Utilisation de la coupe

Prologue de la récursivité