prolog - Establecer Prólogo de intersección Prólogo utilizando no

Question

Estoy tratando de construir un predicado simple que obtenga como entradas dos listas y los resultados son un tercero que consiste en la intersección de las dos primeras. He decidido hacerlo usando declaración lógica. Estoy bastante seguro de que mi lógica es correcta, pero mi predicado no funciona. ¿Algunas ideas?:

element(X,[H|T]) :- 
      X=H
   ;
      element(X,T).

intersection(L1,L2,R) :-
    not((
        element(A,L1),
        not(element(A,L2))
    )),
    not((
        element(A,L1),
        not(element(A,R))
    )).

Por favor, no publique métodos alternativos. Me pregunto por qué este devuelve FALSO en todo momento.

Answer 1

El problema es que not/1 simplemente niega el resultado de tu element/2 . No hace que el element/2 retroceda para encontrar otras instancias para las que not/1 sea ​​cierto el adjunto not/1 .

Considere el siguiente programa.

a(1).
a(2).

b(1).
b(2).
b(3).

Y las siguientes consultas:

1. b(X), not(a(X)) .
2. not(a(X)), b(X) .

El primero produce X = 3 mientras que el segundo produce false . Esto se debe a que la primera consulta crea una instancia de X con 1, luego con 2, luego con 3, hasta que finalmente not(a(X)) tenga éxito.
La segunda consulta crea una instancia de X con 1, a(1) tiene éxito, por lo que not(a(1)) falla. No hay retroceso hecho!

Answer 2

La falta de retroceso debido a la negación, como lo señala @SQB, en realidad no es el único problema con su código. Si juegas un poco con consultas básicas, encontrarás que las no listas y la lista vacía como se indica en @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

Lo primero es lo que generalmente se entiende como intersección. Los otros tres son todos los sublistas de la intersección, incluido el sublista trivial [] . Esto se debe a la forma en que el predicado describe lo que es una intersección: en una intersección no es el caso de que un elemento esté en la primera lista, pero no en la segunda, Y que dicho elemento esté en la primera lista, pero no en la tercera. Esta descripción se ajusta claramente a las tres consultas anteriores, por lo tanto, tienen éxito. Teniendo en cuenta un poco más esta descripción, hay otras consultas de campo notables 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, una cuestión de debate. Las listas [2,2,3] y [2,3] aunque diferentes representan el mismo conjunto {2,3}. Hay una respuesta reciente a una pregunta sobre la unión de Prolog que está elaborando sobre tales aspectos de las respuestas. Y, por supuesto, las listas secundarias 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, por lo tanto, el element(A,L1), not(element(A,L2)) conjunción element(A,L1), not(element(A,L2)) también falla para L1=[] . Por lo tanto la negación envuelta alrededor de él tiene éxito. Lo mismo es cierto para la segunda negación, por lo que [] puede derivarse como intersección. Para ver por qué [2] y [3] tienen é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 variables que no aparecen en el principio 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 los argumentos L1,L2,R hay algunos A que satisfacen los objetivos. 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 considera que L1 no está instanciado y mira los resultados para 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 , descritas por el primer objetivo. Por lo tanto, la conjunción correspondiente en su predicado también tiene que circular. Además de generar resultados, también sería bueno si tal predicado reflejara la naturaleza relacional de Prolog y trabajara al revés también (variable de segundo o tercer argumento). Comparemos su código con tal solución. (Para fines de comparación, el siguiente predicado describe las sublistas de la intersección tal como lo hace su código, para una definición diferente, vea más abajo).

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 los mismos sublistas (incluido [] ):

   ?- list_list_intersection([1,2,3],[2,3,4],I).
I = [] ? ;
I = [2] ? ;
I = [2,3] ? ;
I = [3] ? ;
I = [3,2] ? ;
no

pero sin hacer bucles. Sin embargo, las repeticiones múltiples ya no se producen, ya que los elementos ya emparejados se eliminan mediante list_element_removed / 3. 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) ? ;
...

Así que esta versión corresponde a su código sin los duplicados. Observe cómo 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 recursivamente. Lo que creo que es lo que intentaste lograr utilizando los cuantificadores universales implícitos frente a las reglas de Prolog.

Para volver a un punto al principio 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] solo [2,3] es la intersección. Aquí surge otro problema con su código: si utiliza los elementos de la intersección para describir la relación, ¿cómo se asegura de cubrir todos los elementos que se intersecan? Después de todo, todos los elementos de [2] aparecen en [1,2,3] y [2,3,4] . Una idea obvia sería repasar los elementos de una de las otras listas y describir los que ocurren en ambas como si estuvieran también en la intersección. Aquí hay una variante que usa if_/3 y if_/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 if_/3 es una variante reificada de su elemento de 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" de arriba 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 puedes 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) ? ;
...

Answer 3

Su definición es correcta demasiado general. Admite, por ejemplo, que [] es la intersección de dos listas, lo cual es demasiado general. Es decir, tiene éxito incorrecto para la intersection([],[a],[a]) . Carece de un tercer idioma "para todos" que indica que todos los elementos que están en ambas listas estarán en la lista resultante.

Pero de lo contrario su definición está bien. Para el caso del suelo. 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 listas ni listas parciales:

?- intersection(non_list1,[1,2|non_list2],[3,4|non_list3]).

Para que sea realmente útil y 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 una observación menor, más bien escriba (/+)/1 en lugar de not/1 .