Unión prólogo de la AUBUC

union(A, B, C, U) :-
   union(A, B, V),
   union(C, V, U).

Su definición de se union/3puede mejorar reemplazando

... not(element(X,L)), ...

por

... maplist(dif(X),L), ...

o

... non_member(X, L), ....

non_member(_X, []).
non_member(X, [E|Es]) :-
   dif(X, E),
   non_member(X, Es).

Aquí hay un caso donde se muestra la diferencia:

?- union([A],[B],[C,D]).
   A = C, B = D, dif(C, D).

¿Cómo debe [A]verse [B]tal que su unión contenga 2 elementos?

La respuesta es: deben ser diferentes.

Su versión original falla para esta consulta, sin embargo, tiene éxito para una instancia especializada como:

?- A = 1, B = 2, union([A],[B],[C,D]).

Así que tiene éxito en esto, pero falla en su generalización. Por tanto, no es una relación pura y lógica.

Entonces, ¿está todo bien y perfecto dif/2? Lamentablemente no. @TudorBerariu tiene buenas razones para optar por un recorte, ya que refleja parte de la intención que tenemos sobre la relación. El recorte refleja efectivamente dos intenciones clave

• que la alternativa de no ser miembro ahora está excluida, lo cual es cierto para ciertos modos, como que Arg1 y Arg2 son términos suficientemente instanciados. Una aproximación segura serían los términos básicos.

• que no hay necesidad de mirar más elementos en la lista Arg2, lo cual nuevamente solo es cierto si Arg1 y Arg2 están suficientemente instanciados.

Los problemas solo aparecen cuando los términos no están suficientemente instanciados.

El inconveniente de la definición de OP y la anterior es que ambas son innecesariamente demasiado generales, lo que se puede observar con elementos repetidos en Arg2:

?- union([a,a],[a,a],Zs).
   Zs = [a, a]
;  Zs = [a, a]
;  Zs = [a, a]
;  Zs = [a, a]
;  false.

De hecho, obtenemos |Arg2| ^|Arg1| -1 respuestas redundantes. Así que el corte tenía una buena razón para estar ahí.

Otra razón por la que union/3tal como está no es muy eficiente es que para el caso básico (previsto) deja abiertos puntos de elección innecesarios. Nuevamente, la solución de @TudorBerariu no tiene este problema:

?- union([a],[a],Zs).
   Zs = [a]
;  false.  %    <--- Prolog does not know that there is nothing left

Eliminando la redundancia

La verdadera culpable de tantas respuestas redundantes es la primera regla. element(a,[a,a])(comúnmente llamado member/2) tendrá éxito dos veces.

union([X|Y],L,S) :- element(X,L), union(Y,L,S).
                    ^^^^^^^^^^^^

Aquí hay una definición mejorada:

memberd(X, [X|_Ys]).
memberd(X, [Y|Ys]) :-
   dif(X,Y),          % new!
   memberd(X, Ys).

La regla recursiva, leída de derecha a izquierda, dice lo siguiente:

Supongamos memberd(X, Ys)que ya es cierto para algunos Xy Ys. Teniendo en cuenta eso, y dado que tenemos un ajuste Yque es diferente al X. Entonces

---

podemos concluir que eso también memberd(X, [Y|Ys])es cierto.

Esto ha eliminado las soluciones redundantes. Pero nuestra definición todavía no es muy eficiente: todavía tiene que visitar Arg2 dos veces para cada elemento y luego no puede concluir que no quedan alternativas. En cualquier caso: resistirse a colocar un corte para eliminar esto.

Introducir el determinismo a través de la cosificación.

Compara las definiciones de memberd/2y non_member/2. Aunque describen "lo opuesto" entre sí, se ven muy similares:

non_member(_X, []).
non_member(X, [Y|Ys]) :-
   dif(X,Y),
   non_member(X, Ys).

memberd(X, [X|_Ys]).
memberd(X, [Y|Ys]) :-
   dif(X,Y),         
   memberd(X, Ys).

¡La regla recursiva es la misma! Sólo que el hecho es diferente. Fusionémoslos en una definición, con un argumento adicional que indique si queremos decir memberd( true) o non_member( false):

memberd_t(_X, [], false).
memberd_t(X, [X|_Ys], true).
memberd_t(X, [Y|Ys], Truth) :-
   dif(X, Y),
   memberd_t(X, Ys, Truth).

Ahora, nuestra definición se vuelve un poco más compacta:

unionp([], Ys, Ys).
unionp([X|Xs], Ys, Zs0) :-
  if_( memberd_t(X, Ys), Zs0 = Zs, Zs0 = [X|Zs] ),
  unionp(Xs, Ys, Zs).

memberd_t(_X, [], false).          % see below
memberd_t(X, [Y|Ys], Truth) :-
   if_( X = Y, Truth=true, memberd_t(X, Ys, Truth) ).

Tenga en cuenta la diferencia entre if_(If_1, Then_0, Else_0)y el constructo de control if-then-else ( If_0 -> Then_0 ; Else_0 ). Si bien If_1puede tener éxito varias veces con diferentes valores de verdad (es decir, puede ser tanto verdadero como falso), el constructo de control tiene If_0éxito solo una vez por ser verdadero únicamente.

if_(If_1, Then_0, Else_0) :-
   call(If_1, T),
   (  T == true -> call(Then_0)
   ;  T == false -> call(Else_0)
   ;  nonvar(T) -> throw(error(type_error(boolean,T),_))
   ;  /* var(T) */ throw(error(instantiation_error,_))
   ).

=(X, Y, T) :-
   (  X == Y -> T = true
   ;  X \= Y -> T = false
   ;  T = true, X = Y
   ;  T = false,
      dif(X, Y)                             % ISO extension
      % throw(error(instantiation_error,_)) % ISO strict
   ).

equal_t(X, Y, T) :-
   =(X, Y, T).

Para garantizar que memberd_t/3siempre se beneficie de la indexación del primer argumento, utilice la siguiente definición (gracias a @WillNess):

memberd_t(E, Xs, T) :-
   i_memberd_t(Xs, E, T).

i_memberd_t([], _E, false).
i_memberd_t([X|Xs], E, T) :-
   if_( X = E, T = true, i_memberd_t(Xs, E, T) ).

Dec 08 '2014 13:12 false