Intersección y unión de 2 listas

Luego de investigar con especialistas en esta materia, programadores de deferentes áreas y profesores dimos con la respuesta al problema y la plasmamos en este post.

Solución:

Además, no estoy seguro de por qué está totalmente en contra de los cortes, siempre que 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 al código, solo digo hacer la intersección, pero solo me interesa la primera respuesta. No hay cortes en las propias definiciones de predicado.

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

¿Qué mensaje quiero transmitirles?

• Puedes describir lo que quieras en Prolog con pureza lógica.
• Utilizando if_/3 y (=)/3 una implementación lógicamente pura puede ser
  • ambos eficientes (dejando puntos de elección solo cuando sea necesario)
  • y monótono (lógicamente sólido con respecto a la generalización/especialización).
• La implementación de @falselos predicados if_/3 y (=)/3lo hace usar características meta-lógicas de Prolog internamente, pero (desde el exterior) se comporta lógicamente puro.

La siguiente implementación de list_list_intersection/3 y list_list_union/3 usos list_item_isMember/3 y list_item_subtracted/3definido 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).

Esta es la consulta que publicaste como parte de tu pregunta:

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

Intentemos otra cosa… 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… la conclusión es?

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

---

Editar 2015-04-23

Ninguno de los dos list_list_union(As,Bs,Cs) ni list_list_intersection(As,Bs,Cs) garantizar que Cs no contiene duplicados. Si eso te molesta, el código necesita ser adaptado.

Aquí hay algunas consultas (y respuestas) más con As y/o Bs que contiene 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 como 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 sencillo:

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 está basado en list_setB/2definido aquí.

Ahora veamos los dos 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].

---

Editar 2019-01-30

Aquí hay una consulta adicional tomada del comentario de @GuyCoder (más dos variantes):

?- list_list_unionSet(Xs,[],[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b]
...

?- list_list_unionSet([],Xs,[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b]
...

?- list_list_unionSet(Xs,Ys,[a,b]).
   Xs = [], Ys = [a,b]
;  Xs = [], Ys = [a,b,b]
;  Xs = [], Ys = [a,b,b,b]
...

Con la versión antigua de list_item_subtracted/3las consultas anteriores no terminaron existencialmente.

Con el nuevo lo hacen. Como el tamaño del conjunto de soluciones es infinito, ninguna de estas consultas termina universalmente.

Para hacer trampa un poco menos que mi primera respuesta, podrías usar el encuentra todos predicado de orden superior que hace que Prolog haga 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].

Reseñas y calificaciones

No se te olvide dar visibilidad a esta reseña si te fue de ayuda.

---

---

Utiliza Nuestro Buscador