Prólogo-Encontrar elementos adyacentes en una lista
recursion prolog (5)
Aquí hay una definición que creo que es a largo plazo preferible a la solución de @ repeat:
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)).
Usando un reified y:
'',''(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)).
Estoy tratando de definir un predicado adjacent(X, Y, Zs) que sea verdadero si X e Y son adyacentes en una lista. Mi código es actualmente este:
adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
adjacent(X,Y, Tail).
Funciona para el caso básico de adjacent(c, d, [a, b, c, d, e]) , pero debido al caso base, todos los demás casos también son verdaderos, y estoy atascado en eso.
El otro problema es que si X no es igual a la primera parte de la cabecera de la lista, saltea ambas X e Y y pasa a la siguiente ''X''; por ejemplo, si c no es igual a a , salta a la vez a ayb y comprueba si c es igual a c . Esto es problemático cuando, por ejemplo, la lista es
[a, c, d, e]
porque termina nunca revisando c (creo).
Estoy bastante perdido en la forma de conciliar los dos problemas y convertir mi comprensión lógica de lo que debe ocurrir en el código.
EDITAR: Gracias a la respuesta de Christian Hujer, mi error de caso base ha sido corregido, así que ahora estoy atrapado en el segundo problema.
Creo que tu caso base está mal. En su situación, desea que la recursión termine con un predicado falso, no con un predicado verdadero. Y es lógico: en una lista vacía, no hay elementos adyacentes. Nunca.
El predicado auxiliar adjacent_/5 siempre "se retrasa" por exactamente dos (elementos de la lista):
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+E1if_X0+X1, true, adjacent_(Es, E1, E2, X0, X1)).
Usando SWI-Prolog ejecutamos:
?- 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.
Editar
La definición corregida de adjacent_/5 proporciona respuestas correctas para las siguientes consultas también:
?- 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.
En el intento original de solución:
adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
adjacent(X,Y, Tail).
Como señala @ChristianHujer, la primera cláusula no debería estar allí porque no es verdad. La lista vacía no debe tener elementos adyacentes.
La segunda cláusula también es problemática. Muestra que X e Y son adyacentes en la lista, pero luego se repiten y no solo tienen éxito. Una cláusula adecuada debería ser:
adjacent(X, Y, [X,Y|_]).
Lo que dice que X e Y son adyacentes en la lista si son los primeros dos elementos en la lista, independientemente de cuál sea la cola. Esto también forma un caso base apropiado. Entonces su cláusula recursiva general debería encargarse del resto de los casos:
adjacent(X, Y, [_|Tail]) :-
adjacent(X, Y, Tail).
Esto dice que X e Y son adyacentes en [_|Tail] si están adyacentes en Tail . Esto soluciona el segundo problema que te encuentras.
Por lo tanto, la solución completa sería:
adjacent(X, Y, [X,Y|_]).
adjacent(X, Y, [_|Tail]) :-
adjacent(X, Y, Tail).
Esto tendrá éxito tantas veces como X e Y aparezcan juntas, en ese orden, en la lista.
append/3 @ repeat es más concisa): 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
| ?-
En esta respuesta tratamos de mantenerlo simple, construyendo sobre append/3 :
adjacent(E0, E1, Es) :- append(_, [E0,E1|_], Es).
Consulta de muestra:
?- adjacent(X, Y, [a,b,c,d,e]).
X = a, Y = b ;
X = b, Y = c ;
X = c, Y = d ;
X = d, Y = e ;
false.