56

avs_term_rearranged(AVs, T, AVsR)givenAVsなどTを使用して標準に準拠した方法で記述する方法。これAVsRはAVs、変数がT.

AVsは のような変数名を指定するアトムであり、 は対応する変数A = Vであるという形式の要素のリストです。このようなリストは、read-option (7.10.3) を使用して生成されます。さらに、要素の正確な順序は定義されていません。A'X'Vread_term/2,3variable_names/1

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

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

TAVsプラスいくつかのすべての変数を含む項です。

標準準拠プログラムでは、変数の順序という用語に依存できないことに注意してください (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.]

したがって、 がどのように機能するかは 2 つの方法が考えられます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は線形であるため、これは 2 次です。
  • 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)比較的浅い非決定論のみが関係している場合でも、目標は本質的に非決定論的であること(;)/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).
于 2014-01-28T00:52:07.787 に答える