Te damos la bienvenida a nuestra web, en este lugar vas a hallar la solucíon que buscas.
Solución:
Tu definición es correcto demasiado general. Admite, por ejemplo, que [] es la intersección de dos listas cualesquiera que es demasiado general. Es decir, tiene éxito incorrectamente para intersection([],[a],[a]). Carece de un tercer modismo “para todos” que indique que todos los elementos que están en ambas listas estarán en la lista resultante.
Pero por lo demás, tu definición está bien. Para el caso de tierra. Lo que es un poco inusual es que la intersección es el primer argumento y no el último. Muy irritantes para mí son los nombres de las variables. Creo que R significa “resultado”, por lo tanto, la intersección. Y L1 y L2 son los dos conjuntos para construir la intersección.
Sin embargo, es un poco demasiado general, como muchos predicados de Prolog, piense en append([], non_list, non_list). Aparte de las listas, su definición también admite términos que no son ni listas ni listas parciales:
?- intersection(non_list1,[1,2|non_list2],[3,4|non_list3]).
Para hacerlo realmente util seguro, úsalo así:
?- when(ground(intersection(I, A, B)), intersection(I, A, B)).
más o menos:
?- ( ground(intersection(I, A, B))
-> intersection(I, A, B)
; throw(error(instantiation_error, intersection(I, A, B)))
).
O, usando iwhen/2:
?- iwhen(ground(intersection(I, A, B)), intersection(I, A, B) ).
Como comentario menor, mejor escriba (+)/1 en lugar de not/1.
El problema es ese not/1 simplemente niega el resultado de su element/2. No causa element/2 retroceder para encontrar otras instancias para las que el adjunto not/1 estarán true.
Considere el siguiente programa.
a(1).
a(2).
b(1).
b(2).
b(3).
Y las siguientes consultas:
b(X), not(a(X)).not(a(X)), b(X).
El primero cede X = 3 mientras el segundo cede false. Eso es porque la primera consulta primero instancia X con 1, luego con 2, luego con 3, hasta que finalmente not(a(X)) tiene éxito.
La segunda consulta primero instancia X con 1, a(1) tiene éxito, entonces not(a(1)) falla. ¡No se hace ningún retroceso!
La falta de retroceso debido a la negación, como lo señaló @SQB, en realidad no es el único problema con su código. Si juega un poco con las consultas terrestres, encontrará que las no listas y la lista vacía como lo señala @false tampoco son el único problema. Considere las siguientes consultas:
?- intersection([2,3],[1,2,3],[2,3,4]).
yes
?- intersection([2],[1,2,3],[2,3,4]).
yes
?- intersection([3],[1,2,3],[2,3,4]).
yes
?- intersection([],[1,2,3],[2,3,4]).
yes
El primero es lo que se suele entender por intersección. Los otros tres son sublistas de la intersección, incluida la sublista trivial. []. Esto se debe a la forma en que el predicado describe lo que es una intersección: en una intersección no se da el caso de que un elemento esté en la primera pero no en la segunda lista Y que dicho elemento esté en la primera pero no en la tercera lista. Esta descripción se ajusta claramente a las tres consultas anteriores, por lo que tienen éxito. Jugando un poco más con esta descripción en mente, hay algunas otras consultas terrestres dignas de mención que tienen éxito:
?- intersection([2,2,3],[1,2,3],[2,3,4]).
yes
La cuestión de si la presencia de duplicados en la solución es aceptable o no es, de hecho, un tema bastante debatido. Las listas [2,2,3] y [2,3] aunque diferentes representan el mismo conjunto 2,3. Existe esta respuesta reciente a una pregunta sobre la unión de Prolog que está elaborando sobre tales aspectos de las respuestas. Y, por supuesto, las sublistas de la intersección mencionada anteriormente también pueden contener duplicados o múltiplos:
?- intersection([2,2,2],[1,2,3],[2,3,4]).
yes
Pero, ¿por qué es esto? Para la lista vacía, esto es bastante fácil de ver. La consulta
?- element(A,[]).
no
falla de ahí la conjunción element(A,L1), not(element(A,L2)) también falla para L1=[]. Por tanto, la negación que la envuelve tiene éxito. Lo mismo es true para la segunda negación, en consecuencia [] se puede derivar como intersección. Para ver porque [2] y [3] tener éxito como intersección es útil escribir su predicado como fórmula lógica con los cuantificadores universales escritos explícitamente:
∀L1∀L2∀R∀A(intersection(L1,L2,R) ← ¬ (element(A,L1) ∧ ¬ element(A,L2)) ∧ ¬ (element(A,L1) ∧ ¬ element(A,R)))
Si consulta un libro de texto sobre lógica o uno sobre programación lógica que también muestra el código Prolog como fórmulas lógicas, encontrará que los cuantificadores universales para las variables que no ocurren en el encabezado de la regla se pueden mover al cuerpo como cuantificadores existenciales. En este caso para A:
∀L1∀L2∀R(intersection(L1,L2,R) ← ∃A ( ¬ (element(A,L1) ∧ ¬ element(A,L2)) ∧ ¬ (element(A,L1) ∧ ¬ element(A,R))))
Entonces para todos argumentos L1,L2,R hay algunosA que satisfaga las metas. Lo que explica la derivación de las sublistas de la intersección y las múltiples apariciones de elementos.
Sin embargo, es mucho más molesto que la consulta
?- intersection(L1,[1,2,3],[2,3,4]).
bucles en lugar de producir soluciones. Si consideras eso L1 no se crea una instancia y mira los resultados de la siguiente consulta
?- element(A,L1).
L1 = [A|_A] ? ;
L1 = [_A,A|_B] ? ;
L1 = [_A,_B,A|_C] ? ;
...
queda claro que la consulta
?- element(A,L1),not(element(A,[1,2,3])).
tiene que hacer un bucle debido a las infinitas listas L1, que contienen A, descrito por el primer gol. Por lo tanto, la conjunción correspondiente en su predicado también debe repetirse. Además de producir resultados, también sería bueno si dicho predicado reflejara la naturaleza relacional de Prolog y funcionara también al revés (variable de segundo o tercer argumento). Comparemos su código con dicha solución. (En aras de la comparación, el siguiente predicado describe las sublistas de la intersección tal como lo hace su código, para una definición diferente, consulte más adelante).
Para reflejar su naturaleza declarativa, llamémoslo list_list_intersection / 3:
list_list_intersection(_,_,[]).
list_list_intersection(L1,L2,[A|As]) :-
list_element_removed(L1,A,L1noA),
list_element_removed(L2,A,L2noA),
list_list_intersection(L1noA,L2noA,As).
list_element_removed([X|Xs],X,Xs).
list_element_removed([X|Xs],Y,[X|Ys]) :-
dif(X,Y),
list_element_removed(Xs,Y,Ys).
Al igual que su predicado, esta versión también utiliza los elementos de la intersección para describir la relación. Por lo tanto, está produciendo las mismas sublistas (incluidas []):
?- list_list_intersection([1,2,3],[2,3,4],I).
I = [] ? ;
I = [2] ? ;
I = [2,3] ? ;
I = [3] ? ;
I = [3,2] ? ;
no
pero sin bucle. Sin embargo, ya no se producen múltiples apariciones ya que list_element_removed / 3 elimina los elementos que ya coinciden. Pero las apariciones múltiples en las dos primeras listas coinciden correctamente:
?- list_list_intersection([1,2,2,3],[2,2,3,4],[2,2,3]).
yes
Este predicado también funciona en las otras direcciones:
?- list_list_intersection([1,2,3],L,[2,3]).
L = [2,3|_A] ? ;
L = [2,_A,3|_B],
dif(_A,3) ? ;
L = [2,_A,_B,3|_C],
dif(_A,3),
dif(_B,3) ? ;
...
?- list_list_intersection(L,[2,3,4],[2,3]).
L = [2,3|_A] ? ;
L = [2,_A,3|_B],
dif(_A,3) ? ;
L = [2,_A,_B,3|_C],
dif(_A,3),
dif(_B,3) ? ;
...
Entonces esta versión corresponde a su código sin los duplicados. Note como el elemento A de la intersección aparece explícitamente en el encabezado de la regla donde todos los elementos de la intersección se recorren de forma recursiva. Lo que creo que es lo que intentó lograr utilizando los cuantificadores universales implícitos frente a las reglas de Prolog.
Volviendo a un punto al comienzo de mi respuesta, esto no es lo que comúnmente se entiende como la intersección. Entre todos los resultados list_list_intersection / 3 describe para los argumentos [1,2,3] y [2,3,4] solamente [2,3] es los intersección. Aquí sale a la luz otro problema con su código: si usa los elementos de la intersección para describir la relación, ¿cómo se asegura de cubrir todos los elementos que se cruzan? Después de todo, todos los elementos de [2] ocurre en [1,2,3] y [2,3,4]. Una idea obvia sería recorrer los elementos de una de las otras listas y describir los que ocurren en ambas como si también se encuentran en la intersección. Aquí hay una variante que usa if_ / 3 y memberd_t / 3:
list_list_intersection([],_L2,[]).
list_list_intersection([X|Xs],L2,I) :-
if_(memberd_t(X,L2),
(I=[X|Is],list_element_removed(L2,X,L2noX)),
(I=Is,L2noX=L2)),
list_list_intersection(Xs,L2noX,Is).
Tenga en cuenta que también es posible recorrer los argumentos de la segunda lista en lugar de la primera. El predicado memberd_t / 3 es una variante reificada de su elemento predicado / 2 y list_element_removed / 3 se usa nuevamente en la descripción para evitar duplicados en la solución. Ahora la solución es única
?- list_list_intersection([1,2,3],[2,3,4],L).
L = [2,3] ? ;
no
y las “consultas de problemas” anteriores fallan como se esperaba:
?- list_list_intersection([1,2,3],[2,3,4],[]).
no
?- list_list_intersection([1,2,3],[2,3,4],[2]).
no
?- list_list_intersection([1,2,3],[2,3,4],[3]).
no
?- list_list_intersection([1,2,3],[2,3,4],[2,2,3]).
no
?- list_list_intersection([1,2,3],[2,3,4],[2,2,2]).
no
Y, por supuesto, también puede usar el predicado en las otras direcciones:
?- list_list_intersection([1,2,3],L,[2,3]).
L = [2,3] ? ;
L = [3,2] ? ;
L = [2,3,_A],
dif(_A,1) ? ;
...
?- list_list_intersection(L,[2,3,4],[2,3]).
L = [2,3] ? ;
L = [2,3,_A],
dif(4,_A) ? ;
...
Tienes la posibilidad dar difusión a esta noticia si te fue de ayuda.