Prologue - Trouver les éléments adjacents dans une liste
j'essaie de définir un prédicat adjacent(X, Y, Zs) c'est vrai si X et Y sont adjacents dans une liste. Mon code est actuellement ceci:
adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
adjacent(X,Y, Tail).
Cela fonctionne pour le cas de base de adjacent(c, d, [a, b, c, d, e]), mais en raison du cas de base, tous les autres cas retourne vrai aussi, et je suis coincé sur ce.
l'autre problème est que si X n'est pas égal à la première partie de la tête de liste, alors il passe à la fois X et Y et va à la prochaine 'X'; Par exemple, si c n'est pas égal à , puis il ignore à la fois et b et vérifie si c est égal à c. C'est problématique quand, par exemple, la liste est
[a, c, d, e]
parce qu'il finit par ne jamais vérifier c (je crois).
je suis assez perdu sur la façon de concilier les deux questions et de transformer ma compréhension logique de ce qui doit se produire en code.
EDIT: merci à la réponse de Christian Hujer, ma base l'erreur a été corrigée, donc maintenant je suis juste coincé sur la deuxième question.
5 réponses
Dans la solution d'origine de la tentative:
adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
adjacent(X,Y, Tail).
la seconde clause est également problématique. Il montre que X et Y sont adjacents dans la liste, mais puis revient et ne réussit pas seulement. Une bonne phrase devrait être:
adjacent(X, Y, [X,Y|_]).
Qui dit que X et Y sont adjacentes dans la liste si ce sont les deux premiers éléments de la liste, peu importe ce qu'est la queue. Cela constitue également un cas de base approprié. Alors votre clause générale récursive devrait s'occuper du reste des cas:
adjacent(X, Y, [_|Tail]) :-
adjacent(X, Y, Tail).
Ceci dit que X et Y sont adjacents dans la [_|Tail] s'ils sont adjacents dans la Tail. Cela règle le second problème que vous rencontriez.
ainsi, toute la solution serait:
adjacent(X, Y, [X,Y|_]).
adjacent(X, Y, [_|Tail]) :-
adjacent(X, Y, Tail).
cela réussira autant de fois que X et Y apparaissent ensemble, dans cet ordre, dans la liste.
C'est aussi naturellement soluble avec un DCG (bien que @repeat
append/3 la solution basée est plus concise):
adjacent(X, Y) --> ..., [X, Y], ... .
... --> [] | [_], ... .
adjacent(X, Y, L) :- phrase(adjacent(X, Y), L).
| ?- adjacent(b, c, [a,b,c,d]).
true ? a
(1 ms) no
| ?-
je pense que votre hypothèse de base est faux. Dans votre situation, vous voulez que la récursion se termine avec un faux prédicat, pas avec un vrai prédicat. Et c'est logique: Dans une liste vide, il n'y a pas les éléments adjacents. Jamais.
le prédicat auxiliaire adjacent_/5 toujours "à la traîne" par exactement deux (les éléments de la liste):
adjacent(X0, X1, [E0,E1|Es]) :- adjacent_(Es, E0, E1, X0, X1). adjacent_([], E0, E1, E0, E1). adjacent_([E2|Es], E0, E1, X0, X1) :- if_(E0+E1 = X0+X1, true, adjacent_(Es, E1, E2, X0, X1)).
à l'Aide de SWI-Prolog nous lancer:
?- set_prolog_flag(double_quotes, chars). true. ?- adjacent(a, b, "abab"). true. ?- adjacent(b, c, "abcd"). true. ?- adjacent(X, Y, "abcd"). X = a, Y = b ; X = b, Y = c ; X = c, Y = d.
Modifier
la définition corrigée de adjacent_/5 donne les bonnes réponses pour les requêtes suivantes:
?- adjacent(X, X, [A,B,C]). X = A, A = B ; X = B, B = C, dif(f(C,C),f(A,A)). ?- adjacent(a, X, "aab"). X = a ; X = b. ?- adjacent(a, b, "aab"). true.
adjacent(X0, X1, [E0,E1|Es]) :-
adjacent_(Es, E0, E1, X0, X1).
adjacent_([], E0, E1, E0, E1).
adjacent_([E2|Es], E0, E1, X0, X1) :-
if_(( E0 = X0, E1 = X1 ),
true,
adjacent_(Es, E1, E2, X0, X1)).
à l'Aide d'un réifiée et:
','(A_1, B_1, T) :-
if_(A_1, call(B_1, T), T = false).
;(A_1, B_1, T) :-
if_(A_1, T = true, call(B_1, T)).