prolog - swi - Igualdad de dos listas de variables.

singleton variable in prolog

Question

Cómo definir un predicado meta-lógico que prueba (por lo tanto, tiene éxito o falla solo) si dos listas de variables únicas contienen exactamente las mismas variables que utilizan los incorporados de la norma ISO actual (ISO / IEC 13211-1: 1995 incluyendo Cor.2 ).

Dicho de otra manera, el predicado debería tener éxito si una lista de variables únicas es una permutación de la otra. En analogía con la library(ordsets) , llamemos a este predicado meta-lógico varset_seteq(As, Bs).

Tenga en cuenta que, a diferencia de ord_seteq/2 , este predicado no puede ser simplemente As == Bs .

Answer 1

La solución que propongo utiliza term_variables/2 para verificar si Bs no tiene variables adicionales sobre As y que As no tiene ninguna variable que no aparezca en Bs .

varset_seteq(As, Bs):-
    term_variables(As-Bs, As),
    term_variables(Bs-As, Bs).

La solución anterior puede ser engañada para tener éxito con argumentos que no son conjuntos de variables libres:

 | ?- varset_seteq([A], [a]).

 A = a

 yes

Para evitar eso, la unificación se puede reemplazar con la prueba de equivalencia:

varset_seteq(As, Bs):-
    term_variables(As-Bs, A0),
    A0 == As,
    term_variables(Bs-As, B0),
    B0 == Bs.

Answer 2

Otra solución, menos eficiente que la inteligente solución de Tudor y, por lo tanto, no se recomienda, pero aún así vale la pena mencionarla aquí, ya que veo que se usa en múltiples ocasiones, es:

varset_seteq(As, Bs) :-
    sort(As, Sa), sort(Bs, Sb), Sa == Sb.

Answer 3

Otro enfoque. Si nos proporcionamos estos predicados de orden superior (que son útiles por sí solos),

select_with(_, _, [], []).
select_with(P, X, [Y|Ys], Ys)     :- call(P, X, Y), !.
select_with(P, X, [Y|Ys], [Y|Ks]) :-
    select_with(P, X, Ys, Ks).

foldl(_,[],Vn,Vn).
foldl(P,[X|Xs],V0,Vn) :- 
    call(P,X,V0,V1),
    foldl_(P,Xs,V1,Vn).

entonces podemos definir fácilmente un predicado que es verdadero si cada miembro de una lista tiene un elemento igual en el otro (usando ==/2 ):

members_equal(A, B :-
    foldl(select_with(==), A, B, []).

Este predicado puede ser especializado para el propósito establecido si verificamos que los argumentos entrantes son varsets. Lo siguiente es lo mejor que he podido encontrar en esa dirección (pero se comen bastantes inferencias):

is_varset([]).
is_varset([V|Vs]) :-
    var(V),
    maplist(/==(V), Vs),
    is_varset(Vs).

(Al menos en SWI Prolog, el uso de sort/2 requiere menos inferencias que las anteriores. Supongo que esto se debe a que la clasificación se realiza en C. Además, esta respuesta aún no se acerca a la elegancia del enfoque term_vars/2 — tal es El poder del "ascenso semántico" :)

Answer 4

Si podemos suponer que las dos listas contienen variables únicas, entonces funciona el siguiente uso de doble negación:

varset_seteq(As, Bs) :-
    /+ /+ (numbered_from(As, 1),
           sort(Bs, SBs),
           As == SBs).

numbered_from([], _).
numbered_from([X|Xs], X) :-
    X1 is X + 1,
    numbered_from(Xs, X1).

Esto es similar a la solución de Paulo, pero evita el problema de que la ordenación de variables solo es requerida por ISO / IEC 13211-1 para ser consistente dentro de una sola ejecución de sort/2 .