重新排列变量名称

Question

如何以符合标准的方式写出 avs_term_rearranged(AVs, T, AVsR)，其中 AVs 和 T 已知，使得 AVsR 是 AVs 的排列，元素按照它们在 T 中从左到右出现的顺序进行排列。 AVs 是一个由形如 A = V 的元素组成的列表，其中 A 是指代变量名（例如 'X'）的原子，而 V 则是相应的变量。这样的列表是由带有读取选项 variable_names/1（7.10.3）的 read_term/2,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是不同的变量，则Xterm_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].

- false

---

顺便提一下，在你的问题中，你使用了两次 T 并赋予了不同的含义。为避免混淆，重命名其中一个可能会有所帮助。 - Christian Fritz

@ChristianFritz：我看不出有什么区别。一次，T被用作所寻谓词的参数，另一次它与read_term一起使用，在这种情况下，它会产生T和AVs，使它们适合于谓词。 - false

你能否给出一个输入和期望的输出示例？这是你想要的吗 avs_term_rearranged(['A'=A,'B'=B,'C'=C], A+C+F+B, ['A'=A,'C'=C,'B'=B])？ - Christian Fritz

似乎只要能够弄清如何使用ream_term/3从使用write_term/3写入的流中读取，就可以获得与AVs相符合的T变量表示，并在那一点上，将T变量中不出现在AVs变量中的所有变量丢弃即可。 - Christian Fritz

@ChristianFritz：不确定您的意思。但实际上，read_term / 3和write_term / 3确实使用相同的格式。确定空变量在这里：https://dev59.com/xVzUa4cB1Zd3GeqP57vj#7948525 - false

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

- Per Mildner

---

让我大吃一惊。我本以为要么需要类似@JSchimpf版本的东西（由max_arity和max_integer限制），要么需要sort/2来关联变量及其顺序。无论如何，我很高兴我问了，否则我永远不会找到那个解决方案。也许我的心理障碍在于我希望重新排列现有的(=)/2，而你是在程序上“重构”它们。 - false

一步步进行：在 copy_term/2 之后：AVs 可以被回收。在 bind_names/2 之后：AVs1 可以被回收。在执行 build_vn_list 前：只有两个列表存在，完全没有成对的数据！！ - false

太棒了！我在想我们是否有一个称呼来描述使用双分数据结构和一对对应变量作为“映射器”的技术。 - jschimpf

Answer 2

使用term_variables/2在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。

- jschimpf

Answer 3

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

与之前一样，我们基本上重新排列列表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)
    ).

- jschimpf

---

不错，但不具备可移植性，因为它要求数组是具有无限元数的复合术语。一个较小的问题是它需要任意大小的整数。 - Per Mildner

@Per，老实说，我认为在30年之后，是时候废除复合术语的空间限制了。 - jschimpf

@Per，我不理解你关于“任意大小整数”的评论。这段代码对大整数的要求并不比使用length/2的任何代码更多。事实上，这是少数几种程序类型之一，其中整数严格受限（在32位机器上为2^30左右，在64位机器上为2^61左右）。 - jschimpf

这个问题特别关注的是标准符合的解决方案。标准中没有要求复合项的任意性或能够表示可表达列表长度的足够大的整数。实际上，整数大小很少会成为问题，这就是我写的原因，它的大小不是一个大问题。 - Per Mildner

让我来总结和澄清一下： （1）这是一个完全符合标准的程序； （2）它不需要任意大小的整数； （3）ISO-Prolog 实现在支持的问题实例大小上有所不同； （4）Per 的解决方案更不容易遇到这种实现限制，并且通常更优雅，这就是为什么我点赞并鼓掌的原因。 - jschimpf

Answer 4

这个版本非常简短，使用Prolog prologue中的member/2进行搜索。它的辅助内存消耗非常低，只创建了列表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的（第一个）版本仅为if-then-else实现的(;)/2创建选择点。这两个版本都不会留下任何选择点。 以下是更忠实地模拟@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).

- false