Rearranging variable_names
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).
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)
).
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 traverseT
directly
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).