list - `var(A)` y orden de ejecución

prolog prolog-dif

Question

Ejercicio 09 en esta página http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/ pregunta para crear un predicado que empaqueta elementos repetidos en sublistas.

Una solución directa es simple

pack([], []).
pack([H|T], [I|U]) :-
    split(H, T, I, P),
    pack(P, U).

donde se divide la split(Head, Tail, HeadGroup, Rest) se define como

split(A, [], [A], []).
split(A, [B|T], [A], [B|T]) :- A /= B.
split(A, [A|T], [A|U], B) :- split(A, T, U, B).

que funciona bien y está en línea con la solución de ejemplo proporcionada en la página web mencionada anteriormente.

Donde esta solución falla son las consultas como pack(X, [[a], [b, b]]). . La correspondencia entre dos conjuntos de soluciones es biyectiva (para cada A en el pack(A, B) hay una y solo una B ), por lo que debe haber una mejor solución.

Una forma de resolverlo es cambiar el orden de evaluación, ayudando a prolog a elegir una rama no infinita según el tipo de argumento como sigue

pack([], []).
pack(A, B) :-
  ( var(A) ->
    A = [H|T],
    B = [I|U],
    pack(P, U),
    split(H, T, I, P)
  ; A = [H|T],                                                                                                                                                                                                                                
    B = [I|U],
    split(H, T, I, P),
    pack(P, U)
  ).

Dos preguntas al respecto.

En primer lugar, esto es increíblemente feo, entonces ¿hay una forma mejor de elegir el orden de las reglas dependiendo del tipo de argumento?

En segundo lugar, probablemente sea una pregunta mucho más compleja, ¿hay alguna forma de reescribir la solución sin var(A) y, de no ser así, por qué?

Answer 1

Desde un punto de vista declarativo, las construcciones no monótonas como var/1 y (/=)/2 son muy problemáticas .

¿Por qué? Echale un vistazo:

?- var(A), A=a.
A = a.

?- A=a, var(A).
false.

Entonces, esto rompe la conmutatividad de la conjunción, que es una de las propiedades centrales en las que confiamos cuando razonamos sobre los programas lógicos.

¿Qué pasa con (/=)/2 , que pensaste que expresaría que dos términos son diferentes? Echale un vistazo:

?- X /= Y. false.

No existen dos términos que sean diferentes , ¿sí? Me parece un poco extraño , por decir lo menos, así que aparentemente el predicado realmente significa algo más.

Afortunadamente, en tu caso, la solución es muy fácil . Simplemente use la restricción pura dif/2 para indicar que dos términos son diferentes . Ver prolog-dif para más información. Solo tiene que cambiar una sola línea de código para que su solución sea mucho más general. En lugar de:

split(A, [B|T], [A], [B|T]) :- A /= B.

simplemente use dif/2 :

split(A, [B|T], [A], [B|T]) :- dif(A, B).

Con este cambio, su ejemplo funciona completamente como se esperaba:

?- pack(X, [[a], [b, b]]).
X = [a, b, b] ;
false.

Tenga en cuenta que la literatura de Prolog existente está desactualizada , y la mayoría de estos conjuntos de soluciones provienen de un momento en el que dif/2 ni siquiera estaba disponible en la mayoría de los sistemas Prolog, ciertamente no en los gratuitos.