Reorganizar los nombres de las variables

Cómo escribir de una manera estándar conforme avs_term_rearranged(AVs, T, AVsR) con AVs y T dado tal que AVsR es una permutación de AVs con los elementos dispuestos en el mismo orden como sus variables se producen 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 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 de conformidad 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 y Y son variables que no son idénticos, entonces 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 pedido se mantendrá constante.

NOTA - Si X y Y son variables anónimas, entonces no son términos idénticos (véase 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.]

Así que hay dos maneras posibles de cómo sort/2 funcionará, y uno ni siquiera puede confiar en el éxito de:{[27]]} 

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].
Author: false, 2014-01-23
Source

4 answers

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).
 28
Author: Per Mildner,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-30 22:17:05

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, se puede atravesar T directamente
 10
Author: jschimpf,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-28 00:23:06

Mi respuesta anterior tenía complejidad cuadrática en tiempo de ejecución. 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 no enlazadas no se pueden utilizar como claves para hashing, etc.

Como antes, básicamente reorganizamos la lista AVs de manera que sus elementos tengan el mismo orden que las variables en la lista Xs (obtenida de term_variables/2). La nueva idea aquí es primero calcular una descripción (de tierra) 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)
    ).
 9
Author: jschimpf,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-28 00:08:42

Esta versión es muy corta, usando member/2 (del prólogo del Prolog) para la búsqueda. Tiene muy baja auxiliar consumo de memoria. Solo se crea la lista AVsR. No temporal se crean términos de montón (en implementaciones actuales). Tiene cuadrática overhead en la longitud de AVs, sin embargo.

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 la meta member(AV, AVs) es inherentemente no determinista, incluso si solo el no determinismo relativamente superficial es de @jschimpf, mientras que la (primera) versión crear una opción punto solo para (;)/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. Este, 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).
 5
Author: false,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-28 00:52:07