57

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].
12
  • is T an arbitrary term or is it of the same form? is it, e.g., also obtained from read_term? Jan 25, 2014 at 0:00
  • btw, you are using T twice in your question with different meanings. Might help to rename one of them to avoid confusion. Jan 25, 2014 at 0:02
  • @ChristianFritz: I cannot see a difference. Once, T is used as an argument for the sought predicate, and once it is used with read_term which in this case produces T and AVs such that they fit to the predicate.
    – false
    Jan 25, 2014 at 13:58
  • Could you then give an example input and expeted output? Is this what you have in mind avs_term_rearranged(['A'=A,'B'=B,'C'=C], A+C+F+B, ['A'=A,'C'=C,'B'=B]) ? Jan 25, 2014 at 17:11
  • seems that if you can figure out how to use ream_term/3 to read from a stream that you write to using write_term/3 then you can get a representation of the variables in T that conform with that of AVs, and at that point it's a simple matter of discarding from the T-variables all those that do not appear in the AVs variables. Jan 25, 2014 at 17:51

4 Answers 4

44
+4200
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).
3
  • 1
    Blows my mind. I could have sworn that one needs either something along @JSchimpf's version (limited by max_arity and max_integer) or that sort/2 would be needed to associate the variables and their order. In any case, I'm happy I asked, I would have never found that solution. Maybe the mental block was that I hoped to rearrange the existing (=)/2, whereas you are "reconstructing" them, procedurally speaking.
    – false
    Jan 30, 2014 at 22:46
  • 1
    Going through it step-by-step: After copy_term/2: AVs can be reclaimed. After bind_names/2: AVs1 can be reclaimed. Prior to build_vn_list: Only two lists are present: No pairs at all!!
    – false
    Jan 30, 2014 at 23:13
  • 1
    Brilliant! I was wondering whether we have a name for this technique of using a bipartite data structure with pairs of corresponding variables as a "mapper".
    – jschimpf
    Feb 1, 2014 at 15:59
15

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
0
13

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)
    ).
5
  • 2
    Nice but not portable since it requires Array to be a compound term with unbounded arity. A lesser problem is that it requires arbitrary size integers. Jan 28, 2014 at 16:31
  • 2
    @Per, I honestly think after 30 years it is time to lay arity limits on compound terms to rest.
    – jschimpf
    Feb 1, 2014 at 16:18
  • 1
    @Per, I do not understand your comment about "arbitrary size integers". This code has no more requirement for large integers than any code using length/2. In fact, this is one of the few types of program where integers are strictly bounded (to something like 2^30 on 32-bit, or 2^61 on 64-bit machines).
    – jschimpf
    Feb 1, 2014 at 16:28
  • 3
    The question was specifically about a standard conforming solution. There is nothing in the standard that requires arbitrary arities of compound terms, or integers large enough to represent the length of a representable list. In practice, the integer size is unlikely to be a problem, this is why I wrote that its size is less of a problem. Feb 2, 2014 at 17:04
  • 2
    Let me just summarize and clarify: (1) this is a fully standard-conforming program; (2) it does not require arbitrary sized integers; (3) ISO-Prolog implementations vary in the size of problem instances they support; (4) Per's solution is less likely to run into such implementation limits, and generally more elegant, that's why I upvoted and applauded it.
    – jschimpf
    Feb 3, 2014 at 16:12
11

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.