listing - prolog examples

Prolog union para AUBUC (3)

Empecé a aprender Prolog recientemente y no puedo resolver cómo unir tres listas.

Pude hacer la unión de 2 listas:

puede alguien ayudarme por favor ?

Puede hacer la unión de las dos primeras listas y luego la unión entre ese resultado y el tercero:

union(L1, L2, L3, U):-union(L1, L2, U12), union(U12, L3, U).

Puede mejorar union/3 con un operador de corte:

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

Usar solo predicados con un argumento adicional como memberd_t/3 solo conduce a una reificación débil. Para una reificación fuerte también necesitamos generar restricciones. La reificación fuerte es un enfoque adicional para eliminar el no determinismo.

Pero la reificación fuerte es difícil, una posible forma de archivar esto es usar una instancia CLP(*) que también ha reificado operadores lógicos. Aquí hay un ejemplo si usa CLP(FD) para el problema de la unión. Lamentablemente, esto solo cubre el dominio Z :

Código de reificación fuerte:

member(_, [], 0). member(X, [Y|Z], B) :- (X #= Y) #// C #<==> B, member(X, Z, C). union([], X, X). union([X|Y], Z, T) :- freeze(B, (B==1 -> T=R; T=[X|R])), member(X, Z, B), union(Y, Z, R).

Lo anterior no sufre puntos de elección innecesarios. Aquí hay algunos ejemplos que muestran que esto ya no está sucediendo:

Ejecutando un ejemplo de tierra:

?- union([1,2],[2,3],X). X = [1, 2, 3].

Además, el ejemplo anterior incluso no crea puntos de elección, si usamos variables en alguna parte. Pero podríamos ver muchas restricciones:

Ejecutar un ejemplo no terrestre:

?- union([1,X],[X,3],Y). X#=3#<==>_G316, 1#=X#<==>_G322, _G316 in 0..1, freeze(_G322, (_G322==1->Y=[X, 3];Y=[1, X, 3])), _G322 in 0..1. ?- union([1,X],[X,3],Y), X=2. X = 2, Y = [1, 2, 3].

Como no formulamos algunos invariantes de entrada, el intérprete no puede ver que producir restricciones en el caso anterior no tiene ningún sentido. Podemos usar la restricción all_different/1 para ayudar al intérprete un poco:

Proporcionar invariantes:

?- all_different([1,X]), all_different([X,3]), union([1,X],[X,3],Y). Y = [1, X, 3], X in inf..0//2//4..sup, all_different([X, 3]), all_different([1, X]).

Pero no deberíamos esperar demasiado de este ejemplo singular. Dado que el CLP(FD) y el freeze/2 es solo un procedimiento de decisión incompleto para proposiciones y ecuaciones Z, el enfoque podría no funcionar tan bien como en todas las situaciones.

Adiós

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

Su definición de union/3 puede mejorarse reemplazando

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

por

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

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

Aquí hay un caso donde la diferencia muestra:

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

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

La respuesta es: deben ser diferentes.

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

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

Entonces tiene éxito para esto, pero falla para una generalización de la misma. Por lo tanto, no es una relación pura y lógica.

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

que la alternativa de no ser miembro ahora está excluida, lo cual es cierto para ciertos modos, como Arg1 y Arg2 son términos suficientemente instanciados. Una aproximación segura sería términos básicos.
que no hay necesidad de mirar más elementos en la lista Arg2, lo que de nuevo solo es cierto si Arg1 y Arg2 están suficientemente instanciados.

Los problemas solo se muestran 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. Entonces el corte tenía una buena razón para estar allí.

Otra razón por la cual union/3 en su forma actual no es muy eficiente es que para el caso de tierra (previsto) deja abiertos puntos de elección innecesarios. Nuevamente, la solución de @ TudorBerariu no tiene este problema:

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

Eliminar la redundancia

El verdadero 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, que se lee de derecha a izquierda, dice lo siguiente:

Suponga que memberd(X, Ys) ya es cierto para algunas X e Ys . Dado eso, y dado que tenemos un ajuste Y que es diferente de X Entonces
podemos concluir que también memberd(X, [Y|Ys]) es verdadero.

Entonces esto ha eliminado las soluciones redundantes. Pero nuestra definición aún 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: resiste colocar un corte para eliminar esto.

Introducción del determinismo a través de la reificación.

Compare las definiciones de memberd/2 y non_member/2 . Aunque describen "lo opuesto" el uno del otro, 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! Solo el hecho es diferente. memberd en una definición, con un argumento adicional que memberd 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) ).

Observe la diferencia entre if_(If_1, Then_0, Else_0) y la construcción de control if-then-else ( If_0 -> Then_0 ; Else_0 ) . Si bien If_1 puede tener éxito varias veces con diferentes valores de verdad (es decir, puede ser tanto verdadero como falso), la construcción de control hace que If_0 éxito solo una vez por ser solo verdadero.

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 asegurarse de que memberd_t/3 siempre se beneficiará de la indexación de 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) ).