concatenate - prolog add element to list

La unión de Prolog falla

Question

Estoy tratando de entender el uso de la unión (el predicado incorporado) en Prolog. En muchos casos, parece fallar cuando debería tener éxito. Parece que tiene algo que ver con el orden de los elementos de las listas. Todos los casos siguientes fallan (vuelven con "falso").

?- union([1,2,3],[],[2,3,1]).  
?- union([1,5,3], [1,2], [1,5,3,2]). 
?- union([4,6,2,1], [2], [1,2,4,6]).
?- union([1,2], [], [2,1]).

¿No deberían todos estos ser verdad? Cualquier explicación sobre por qué estos casos siguen fallando sería muy útil.

Además: ¿Por qué no funciona lo siguiente y encuentra la lista correcta para A?

 ?- union([1,5,3], A, [4,1,5,3,2]).  /** comes back with "fail." */

Answer 1

Hay un par de problemas aquí. Declarativo y procesal. Comencemos con los declarativos, están realmente sentados un poco más profundo. Los aspectos de procedimiento se pueden manejar fácilmente con técnicas de programación apropiadas, como en esta respuesta .

Cuando consideramos las propiedades declarativas de un predicado, consideramos su conjunto de soluciones. Entonces pretendemos que todo lo que nos importa es qué soluciones describirá el predicado. Ignoramos completamente cómo se implementa todo esto. Para predicados muy simples, es una simple enumeración de hechos, como una tabla de base de datos. Todo es obvio en tales situaciones. Se vuelve mucho más intuitivo si el conjunto de soluciones es infinito. Y esto sucede tan fácilmente. Piensa en la consulta

?- length(Xs,1).

Esta consulta inofensiva pide todas las listas de longitud uno. ¡Todos ellos! Déjame contar, ¡eso es infinitamente!

Antes de ver la respuesta real que produce Prolog, piense qué haría en tal situación. ¿Cómo responderías esa consulta? Algunos de mis débiles intentos

?- length(Xs, 1).
   Xs = [1]
;  Xs = [42]
;  Xs = [ben+jerry]
;  Xs = [feel([b,u,r,n])]
;  Xs = [cromu-lence]
;  Xs = [[[]]]
;  ... % I am running out of imagination

¿Prolog debería producir todos esos infinitos valores? ¿Cuánto tiempo tomaría esto? ¿Cuánto tiempo tienes para mirar las paredes del texto? Tu vida no es suficiente.

Controlando el número de soluciones, desde soluciones hasta respuestas

Hay una salida: ¡la variable lógica!

?- length(Xs, 1).
Xs = [_A].
%     ^^

¡Este pequeño _A nos permite colapsar todas las soluciones extrañas en una sola respuesta !

Así que aquí realmente tuvimos mucha suerte: domesticamos el infinito con esta bonita variable.

Ahora volvamos a tu relación. Ahí, queremos representar conjuntos como listas. Las listas claramente no son conjuntos per se . Considere la lista [a,a] y la lista [a] . Si bien son diferentes, están destinados a representar el mismo conjunto. Piénselo: ¿Cuántas representaciones alternativas hay para [a] ? Sí, infinitamente muchos. Pero ahora, la variable lógica no puede ayudarnos a representarlos a todos de manera compacta ¹ . Por lo tanto, debemos enumerarlos uno a uno. Pero si tenemos que enumerar todas esas respuestas, prácticamente todas las consultas no terminarán debido a infinitas soluciones para enumerar explícitamente. OK, algunos todavía lo harán:

?- union([], [], Xs).
   Xs = [].

Y todas las consultas en el terreno. Y todas las consultas que fallan Pero una vez que tenemos una variable como

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

ya estamos profundamente inmersos en la no terminación.

Entonces, dado eso, tenemos que tomar algunas decisiones. De alguna manera necesitamos domesticar ese infinito. Una idea es considerar un subconjunto de la relación real que se inclina de algún modo hacia un lado. Si queremos hacer preguntas como union([1,2],[3,4], A3) entonces es bastante natural imponer un subconjunto donde tenemos esta dependencia funcional

A1, A2 → A3

Con esta dependencia funcional ahora determinamos exactamente un valor para A3 para cada par de A1 , A2 . Aquí hay unos ejemplos:

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

Tenga en cuenta que Prolog siempre pone a . un final Eso significa que Prolog dice:

Dixi! He hablado. No hay más soluciones.

(Otros Prologs harán un "No" al final). Como consecuencia, las consultas (de sus comentarios) ahora fallan:

?- union([1,5,3], [1,2], [1,5,3,2]).
false.

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

Entonces, imponer esa dependencia funcional ahora restringe drásticamente el conjunto de soluciones. Y esa restricción fue una decisión arbitraria del implementador. ¡Podría haber sido diferente! A veces, los duplicados se eliminan, a veces no. Si A1 y A2 son listas libres duplicadas, el resultado A3 también será duplicado.

Después de observar su implementación, parece que se cumple lo siguiente (no es necesario hacer esto, la documentación debe ser lo suficientemente buena, bueno, no lo es): los elementos en el último argumento están estructurados de la siguiente manera y en ese orden:

1. Los elementos de A1 que no ocurren en A2 también. En el orden relativo de A1.

2. Todos los elementos de A2 en su orden original.

Por lo tanto, con esta dependencia funcional, se han introducido más propiedades. ¡Como que A2 siempre es un sufijo de A3! En consecuencia, lo siguiente no puede ser cierto, porque no hay un sufijo de A3 que haga verdadera esta consulta:

?- union([1,5,3], A2, [4,1,5,3,2]).
false.

Y aún hay más irregularidades que se pueden describir a nivel declarativo. A menudo, en aras de la eficiencia, las relaciones son demasiado generales. Me gusta:

?- union([],non_list,non_list).

Tales preocupaciones a menudo se borran al observar que solo nos interesan los objetivos con argumentos que son listas (como [a,b] ) o listas parciales (como [a,b|Xs] ).

De todas formas. Finalmente, hemos descrito todas las propiedades declarativas que esperamos. Ahora viene la siguiente parte: ¡esa relación debería implementarse adecuadamente! ¡De nuevo nos espera un nuevo grupo de problemas!

Con la library(lists) de SWI, obtengo:

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

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

Lo cual es realmente incorrecto: esto solo se puede entender procedimentalmente, mirando la implementación real. Esto ya no es una relación limpia. ¡Pero este problema puede solucionarse !

Puede evitar los problemas de corrección al adherirse al subconjunto monótono y puro de Prolog. Ver arriba para más.

_{1) Para decir la verdad, sería posible representar ese conjunto infinito con alguna clase de restricciones. Pero el mero hecho de que no haya una sola biblioteca para conjuntos proporcionados por los sistemas Prolog actuales debería dejar en claro que esta no es una opción obvia.}