56

如何avs_term_rearranged(AVs, T, AVsR)使用给定的标准以符合标准的方式编写AVs，T这AVsR就是AVs元素的排列顺序相同，因为它们的变量以从左到右的顺序出现在T.

AVs是形式元素的列表，A = V其中A是指定变量名称的原子，如'X'并且V是相应的变量。此类列表由read_term/2,3带有 read-option variable_names/1(7.10.3) 生成。此外，没有定义元素的精确顺序。

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

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

T是一个包含所有变量AVs以及更多变量的术语。

请注意，在符合标准的程序中，不能依赖于变量的术语顺序（7.2.1）：

7.2.1 变量

如果X和Y是不相同的变量，则X term_precedes Y应依赖于实现，除非在创建排序列表（7.1.6.5、8.10.3.1 j）期间，排序应保持不变。

注——如果X和Y都是匿名变量，那么它们不是相同的项（见 6.1.2 a）。

以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.]

因此，有两种可能的sort/2工作方式，一种甚至不能依赖于：

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

举个例子：

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

4 回答 4

43 
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).
于 2014-01-30T22:17:05.983 回答
15

使用term_variables/2on以所需顺序T获取包含变量的列表。Xs然后用 的元素构建一个列表AVs，但按该顺序。

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

笔记：

  • 这是二次的，因为pick/4是线性的
  • term_variables/2不是绝对必要的，你可以T直接遍历
于 2014-01-26T23:24:00.880 回答
13

我之前的答案具有二次运行时复杂性。如果这是一个问题，这里有一个线性替代方案。这有点棘手的原因是未绑定的变量不能用作散列等的键。

和以前一样，我们基本上重新排列列表AVs，使其元素与列表中的变量具有相同的顺序Xs（从 获得term_variables/2）。这里的新想法是首先计算所需置换 ( APs) 的（基础）描述，然后AV使用该描述构造置换。

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)
    ).
于 2014-01-28T00:08:42.193 回答
11

这个版本很短，使用 member/2 （来自 Prolog 序言）进行搜索。它具有非常低的辅助内存消耗。仅AVsR创建列表。没有创建临时堆项（在当前实现上）。但是，它在 的长度上有二次开销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).

另一方面是member(AV, AVs)目标本质上是非确定性的，即使只涉及相对浅的非确定性，而 @jschimpf 的（第一个）版本确实为(;)/2if-then-else-implementation 创建了一个选择点。两个版本都没有留下任何选择点。

这是一个更忠实地模拟@jschimpf 想法的版本。但是，这现在会创建留在堆上的辅助项。

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).
于 2014-01-28T00:52:07.787 回答