prolog - sintaxis - Reorganizar variables_names

prolog tutorial

Question

Cómo escribir de una manera estándar conforme avs_term_rearranged(AVs, T, AVsR) con avs_term_rearranged(AVs, T, AVsR) y T dados tales que AVsR es una permutación de AVs con los elementos dispuestos en el mismo orden en que sus variables ocurren en orden de izquierda a derecha en T

AVs es una lista de elementos de la forma A = V donde A es un átomo que designa un nombre de variable como ''X'' y V es una variable correspondiente. Dichas listas son producidas por read_term/2,3 con la opción de lectura variable_names/1 (7.10.3). Además, el orden preciso de los elementos no está definido.

| ?- read_term(T,[variable_names(AVs)]).
A+B+A+_+C.

AVs = [''A''=A,''B''=B,''C''=C]
T = A+B+A+_+C

T es un término que contiene todas las variables de AVs más algunas más.

Tenga en cuenta que en un programa estándar no se puede confiar en el orden de los términos para las variables (7.2.1):

7.2.1 Variable

Si X e Y son variables que no son idénticas, X term_precedes Y será dependiente de la implementación, excepto que durante la creación de una lista ordenada (7.1.6.5, 8.10.3.1 j) el ordenamiento se mantendrá constante.

NOTA - Si X e Y son ambas variables anónimas, entonces no son términos idénticos (ver 6.1.2 a).

Considere como un ejemplo de 8.4.3.4 :

sort([f(U),U,U,f(V),f(U),V],L).
   Succeeds, unifying L with [U,V,f(U),f(V)] or
   [V,U,f(V),f(U)].
   [The solution is implementation dependent.]

Entonces, hay dos maneras posibles de cómo sort/2 funcionará, y uno ni siquiera puede confiar en el éxito de:

sort([f(U),U,U,f(V),f(U),V],L), sort(L, K), L == K.

Como ejemplo:

?- avs_term_rearranged([''A''=A,''B''=B,''C''=C], A+C+F+B, AVsR).
   AVsR = [''A''=A,''C''=C,''B''=B].

Answer 1

Esta versión es muy corta, utilizando member/2 (del prólogo de Prolog) para la búsqueda. Tiene un consumo de memoria auxiliar muy bajo. Solo se crea la lista AVsR . No se crean términos de montón temporales (en las implementaciones actuales). Sin embargo, tiene una carga cuadrática en la longitud de los AVs .

avs_term_rearranged(AVs, T, AVsR) :-
   term_variables(T, Vs),
   rearrange(Vs, AVs, AVsR).

rearrange([], _, []).
rearrange([V|Vs], AVs, AVsR0) :-
   ( member(AV, AVs),
     AV = (_=Var), V == Var ->
      AVsR0 = [AV|AVsR]
   ;  AVsR0 = AVsR
   ),
   rearrange(Vs, AVs, AVsR).

Otro aspecto es que el objetivo del member(AV, AVs) es intrínsecamente no determinista, incluso si solo está involucrado no determinismo relativamente superficial, mientras que la versión de @ jschimpf (primera) crea un punto de elección solo para el (;)/2 de la implementación if-then-else. Ambas versiones no dejan ningún punto de elección atrás.

Aquí hay una versión que simula más fielmente la idea de @ jschimpf. Esto, sin embargo, ahora crea términos auxiliares que quedan en el montón.

rearrange_js([], _, []).
rearrange_js([V|Vs], AVs0, AVsR0) :-
   ( select(AV, AVs0, AVs),
     AV = (_=Var), V == Var ->
      AVsR0 = [AV|AVsR]
   ;  AVsR0 = AVsR,
      AVs0 = AVs
   ),
   rearrange_js(Vs, AVs, AVsR).

Answer 2

Mi respuesta anterior tenía una complejidad de tiempo de ejecución cuadrática. Si eso es un problema, aquí hay una alternativa lineal. La razón por la que esto es un poco complicado es que las variables independientes no se pueden usar como claves para hashing, etc.

Como antes, básicamente reorganizamos los AVs la lista de forma que sus elementos tengan el mismo orden que las variables en la lista Xs (obtenidas de term_variables/2 ). La nueva idea aquí es primero calcular una descripción (terrestre) de la permutación requerida ( APs ), y luego construir la permutación de AV usando esta descripción.

avs_term_rearranged(AVs, T, AVRs) :-
    term_variables(T, Xs),
    copy_term(AVs-Xs, APs-Ps),
    ints(Ps, 0, N),
    functor(Array, a, N),
    distribute(AVs, APs, Array),
    gather(1, N, Array, AVRs).

ints([], N, N).
ints([I|Is], I0, N) :- I is I0+1, ints(Is, I, N).

distribute([], [], _).
distribute([AV|AVs], [_=P|APs], Array) :-
    nonvar(P),
    arg(P, Array, AV),
    distribute(AVs, APs, Array).

gather(I, N, Array, AVRs) :-
    ( I > N ->
        AVRs = []
    ;
        arg(I, Array, AV),
        I1 is I+1,
        ( var(AV) -> AVRs=AVRs1 ; AVRs = [AV|AVRs1] ),
        gather(I1, N, Array, AVRs1)
    ).

Answer 3

Use term_variables/2 en T para obtener una lista Xs con variables en el orden deseado. Luego construya una lista con los elementos de AVs , pero en ese orden.

avs_term_rearranged(AVs, T, AVRs) :-
    term_variables(T, Xs),
    pick_in_order(AVs, Xs, AVRs).

pick_in_order([], [], []).
pick_in_order(AVs, [X|Xs], AVRs) :-
    ( pick(AVs, X, AV, AVs1) ->
        AVRs = [AV|AVRs1],
        pick_in_order(AVs1, Xs, AVRs1)
    ;
        pick_in_order(AVs, Xs, AVRs)
    ).

pick([AV|AVs], X, AX, DAVs) :-
    (_=V) = AV,
    ( V==X ->
        AX = AV,
        DAVs = AVs
    ;
        DAVs = [AV|DAVs1],
        pick(AVs, X, AX, DAVs1)
    ).

Notas:

• esto es cuadrático porque pick/4 es lineal
• term_variables/2 no es estrictamente necesario, puede atravesar T directamente

Answer 4

avs_term_rearranged(AVs, T, AVsR) :-
    term_variables(T, Vs),
    copy_term(Vs+AVs, Vs1+AVs1),
    bind_names(AVs1),
    build_vn_list(Vs, Vs1, AVsR).

bind_names([]).
bind_names([N=V|AVs]) :-
    N = V,
    bind_names(AVs).

build_vn_list([], [], []).
build_vn_list([V|Vs],[N|Ns],NVs) :-
    ( atom(N) ->
      NVs = [N=V|NVs1]
    ; var(N) ->
      NVs = NVs1
    ),
    build_vn_list(Vs, Ns, NVs1).