Intersección y unión de 2 listas

Estoy comenzando a aprender prólogo (uso SWI-prolog) e hice un ejercicio simple en el que tengo 2 listas y quiero calcular su intersección y unión. Aquí está mi código que funciona bastante bien, pero me preguntaba si hay una mejor manera de hacerlo, ya que no me gusta usar el operador CUT .

intersectionTR(_, [], []). intersectionTR([], _, []). intersectionTR([H1|T1], L2, [H1|L]):- member(H1, L2), intersectionTR(T1, L2, L), !. intersectionTR([_|T1], L2, L):- intersectionTR(T1, L2, L). intersection(L1, L2):- intersectionTR(L1, L2, L), write(L). unionTR([], [], []). unionTR([], [H2|T2], [H2|L]):- intersectionTR(T2, L, Res), Res = [], unionTR([], T2, L), !. unionTR([], [_|T2], L):- unionTR([], T2, L), !. unionTR([H1|T1], L2, L):- intersectionTR([H1], L, Res), Res \= [], unionTR(T1, L2, L). unionTR([H1|T1], L2, [H1|L]):- unionTR(T1, L2, L). union(L1, L2):- unionTR(L1, L2, L), write(L). 

Tenga en cuenta que quiero tener solo 1 resultado, no múltiples resultados (incluso si es correcto) para ejecutar el código con esto:

 ?- intersect([1,3,5,2,4] ,[6,1,2]). 

debe salir con:

 [1,2] true. 

y no con

 [1,2] true ; [1,2] true ; etc... 

Lo mismo debe ser válido para el predicado de unión.
Como dije, mi código funciona bastante bien, pero sugiera mejores formas de hacerlo.
Gracias

Además, no estoy seguro de por qué está muerto contra los recortes, siempre y cuando su eliminación no cambie el significado declarativo del código, según su enlace. Por ejemplo:

 inter([], _, []). inter([H1|T1], L2, [H1|Res]) :- member(H1, L2), inter(T1, L2, Res). inter([_|T1], L2, Res) :- inter(T1, L2, Res). test(X):- inter([1,3,5,2,4], [6,1,2], X), !. test(X). X = [1, 2]. 

En el bit de prueba donde llamo el código, solo digo que hagas la intersección, pero solo estoy interesado en la primera respuesta. No hay recortes en las definiciones de predicado en sí.

Lo siguiente se basa en mi respuesta anterior a Eliminar duplicados en la lista (Prólogo) ; la idea básica se basa, a su vez, en la respuesta de @ false a la unión Prolog para AUBUC .

¿Qué mensaje quiero transmitirle?

  • Puede describir lo que quiere en Prolog con pureza lógica.
  • Usando if_/3 y (=)/3 una implementación lógicamente pura puede ser
    • ambos eficientes (dejando atrás los puntos de elección solo cuando sea necesario)
    • y monótono (lógicamente sano con respecto a la generalización / especialización).
  • La implementación de los predicados de if_/3 y (=)/3 usa características de Prolog meta-lógicas internamente, pero (desde el exterior) se comporta lógicamente pura .

La siguiente implementación de list_list_intersection/3 y list_list_union/3 usa list_item_isMember/3 y list_item_subtracted/3 , definidos en una respuesta anterior :

 list_list_union([],Bs,Bs). list_list_union([A|As],Bs1,[A|Cs]) :- list_item_subtracted(Bs1,A,Bs), list_list_union(As,Bs,Cs). list_list_intersection([],_,[]). list_list_intersection([A|As],Bs,Cs1) :- if_(list_item_isMember(Bs,A), Cs1 = [A|Cs], Cs1 = Cs), list_list_intersection(As,Bs,Cs). 

Aquí está la consulta que publicó como parte de su pregunta:

 ?- list_list_intersection([1,3,5,2,4],[6,1,2],Intersection). Intersection = [1, 2]. % succeeds deterministically 

Probemos algo más … Las siguientes dos consultas deberían ser lógicamente equivalentes:

 ?- A=1,B=3, list_list_intersection([1,3,5,2,4],[A,B],Intersection). A = 1, B = 3, Intersection = [1, 3]. ?- list_list_intersection([1,3,5,2,4],[A,B],Intersection),A=1,B=3. A = 1, B = 3, Intersection = [1, 3] ; false. 

Y … ¿el resultado final es?

  • Con código puro, es fácil mantenerse del lado de la solidez lógica .
  • El código impuro, por otro lado, a menudo actúa como “hace lo que debería” a primera vista, pero muestra todo tipo de comportamiento ilógico con consultas como las que se muestran arriba.

Editar 2015-04-23

Ni list_list_union(As,Bs,Cs) ni list_list_intersection(As,Bs,Cs) garantizan que Cs no contiene duplicados. Si eso te molesta, el código debe ser adaptado.

Aquí hay algunas consultas más (y respuestas) con As y / o Bs contienen duplicados:

 ?- list_list_intersection([1,3,5,7,1,3,5,7],[1,2,3,1,2,3],Cs). Cs = [1, 3, 1, 3]. ?- list_list_intersection([1,2,3],[1,1,1,1],Cs). Cs = [1]. ?- list_list_union([1,3,5,1,3,5],[1,2,3,1,2,3],Cs). Cs = [1, 3, 5, 1, 3, 5, 2, 2]. ?- list_list_union([1,2,3],[1,1,1,1],Cs). Cs = [1, 2, 3]. ?- list_list_union([1,1,1,1],[1,2,3],Cs). Cs = [1, 1, 1, 1, 2, 3]. 

Editar 2015-04-24

En aras de la exhaustividad, así es cómo podríamos hacer cumplir que la intersección y la unión son conjuntos, es decir, listas que no contienen ningún elemento duplicado.

El siguiente código es bastante directo:

 list_list_intersectionSet([],_,[]). list_list_intersectionSet([A|As1],Bs,Cs1) :- if_(list_item_isMember(Bs,A), Cs1 = [A|Cs], Cs1 = Cs), list_item_subtracted(As1,A,As), list_list_intersectionSet(As,Bs,Cs). list_list_unionSet([],Bs1,Bs) :- list_setB(Bs1,Bs). list_list_unionSet([A|As1],Bs1,[A|Cs]) :- list_item_subtracted(As1,A,As), list_item_subtracted(Bs1,A,Bs), list_list_unionSet(As,Bs,Cs). 

Tenga en cuenta que list_list_unionSet/3 se basa en list_setB/2 , definido aquí .

Ahora veamos list_list_intersectionSet/3 y list_list_unionSet/3 en acción:

 ?- list_list_unionSet([1,2,3,1,2,3,3,2,1],[4,5,6,2,7,7,7],Xs). Xs = [1, 2, 3, 4, 5, 6, 7]. ?- list_list_intersectionSet([1,2,3,1,2,3,3,2,1],[4,5,6,2,7,7,7],Xs). Xs = [2]. 

Para hacer trampa un poco menos que mi primera respuesta, podría usar el predicado de orden superior findall que obtiene Prolog para hacer la recursión por usted:

 4 ?- L1=[1,3,5,2,4], L2=[6,1,2], findall(X, (nth0(N, L1, X), member(X, L2)), Res). L1 = [1, 3, 5, 2, 4], L2 = [6, 1, 2], Res = [1, 2]. 

Si el objective es simplemente ‘hacer el trabajo’, swi prolog ha incorporado primitivas para exactamente este propósito:

 [trace] 3 ?- intersection([1,3,5,2,4] ,[6,1,2], X). intersection([1,3,5,2,4] ,[6,1,2], X). X = [1, 2]. [trace] 4 ?- union([1,3,5,2,4] ,[6,1,2], X). X = [3, 5, 4, 6, 1, 2]. 

Y finalmente (realmente), podría usar findall para encontrar todas las soluciones, luego use nth0 para extraer la primera, que le dará el resultado que desea sin cortes, y mantiene los predicados agradables y limpios, sin tener ningún predicado adicional para trap / stop prolog haciendo lo que mejor hace: retroceder y encontrar respuestas múltiples.

Edición: es discutible que incluir predicados adicionales en la ‘lógica central’ para evitar la generación de resultados múltiples sea tan feo / confuso como usar los cortes que intenta evitar. Pero tal vez este sea un ejercicio académico para demostrar que se puede hacer sin usar predicados de orden superior como findall, o la intersección / unión incorporada.

 inter([], _, []). inter([H1|T1], L2, [H1|Res]) :- member(H1, L2), inter(T1, L2, Res). inter([_|T1], L2, Res) :- inter(T1, L2, Res). test(First):- findall(Ans, inter([1,3,5,2,4], [6,1,2], Ans), Ansl), nth0(0, Ansl, First). 

Sé que esta publicación es muy antigua, pero encontré una solución con una encoding mínima.

% de intersección de intersección ([], L1, L2, L3). intersección ([H | T], L2, L3, [H | L4]): – miembro (H, L2), intersección (T, L3, L3, L4). % miembro miembro (H, [H | T]). miembro (X, [H | T]): – miembro (X, T).

Para probar el código anterior, no debe ingresar L3. Aquí hay un ejemplo.

? – intersección ([w, 4, g, 0, v, 45,6], [x, 45, d, w, 30,0], L). L = [w, 0, 45].

% Elemento X está en la lista?

pert (X, [X | _]).

pert (X, [_ | L]): – pert (X, L).

% Unión de dos listas

unión ([], L, L).

unión ([X | L1], L2, [X | L3]): – \ + pert (X, L2), unión (L1, L2, L3).

unión ([_ | L1], L2, L3): – unión (L1, L2, L3).

% Intersección de dos listas

inter ([], _, []).

inter ([X | L1], L2, [X | L3]): – pert (X, L2), inter (L1, L2, L3).

inter ([_ | L1], L2, L3): – inter (L1, L2, L3).