Rearranging variable_names

Question

The bounty expires in 10 hours. Answers to this question are eligible for a +500 reputation bounty. false wants to reward an existing answer.

How to write in a standard conforming manner avs_term_rearranged(AVs, T, AVsR) with given AVs and T such that AVsR is a permutation of AVs with the elements arranged in same order as their variables occur in left-to-right order in T.

AVs is a list of elements of the form A = V where A is an atom designating a variable name like 'X' and V is a corresponding variable. Such lists are produced by read_term/2,3 with the read-option variable_names/1 (7.10.3). Additionally, the precise order of elements is not defined.

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

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

T is a term that contains all variables of AVs plus some more.

Note that in a standard conforming program one cannot rely on the term order for variables (7.2.1):

7.2.1 Variable

If X and Y are variables which are not identical then X term_precedes Y shall be implementation dependent except that during the creation of a sorted list (7.1.6.5, 8.10.3.1 j) the ordering shall remain constant.

NOTE — If X and Y are both anonymous variables then they are not identical terms (see 6.1.2 a).

Consider as an example from 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.]

So there are two possible ways how sort/2 will work, and one cannot even rely on the success of:

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

As an example:

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

Answer 1

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).

Answer 2

My previous answer had quadratic runtime complexity. If that's a problem, here is a linear alternative. The reason this is a bit tricky is that unbound variables cannot be used as keys for hashing etc.

As before, we basically rearrange the list AVs such that its elements have the same order as the variables in the list Xs (obtained from term_variables/2). The new idea here is to first compute a (ground) description of the required permutation (APs), and then construct the permutation of AV using this description.

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

This version is very short, using member/2 (from the Prolog prologue) for the search. It has very low auxiliary memory consumption. Only the list AVsR is created. No temporary heap-terms are created (on current implementations). It has quadratic overhead in the length of AVs, though.

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).

Another aspect is that the member(AV, AVs) goal is inherently non-deterministic, even if only relatively shallow non-determinism is involved, whereas @jschimpf's (first) version does create a choice point only for the (;)/2 of the if-then-else-implementation. Both versions do not leave any choice points behind.

Here is a version more faithfully simulating @jschimpf's idea. This, however, now creates auxiliary terms that are left on the heap.

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 4

Use term_variables/2 on T to obtain a list Xs with variables in the desired order. Then build a list with the elements of AVs, but in that order.

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)
    ).

Notes:

• this is quadratic because pick/4 is linear
• term_variables/2 is not strictly necessary, you could traverse T directly