4

差分リストは、プロローグで変数が不変であるという事実を「回避」する手段ですか?

つまり、差分リストを使用して追加を実装する場合:

diff_append(OpenList, Hole, L2) :-
    Hole = L2.

そして実行します：

X=[a,b,c|Hole], diff_append(X, Hole, [d,e,f]).

X は、ある意味で、変更可能な変数として使用されています。私たちの意図と目的のために、それは変更されましたか?

言い換えれば、新しいリスト、たとえば Z (不変) を作成する必要がなく、X (可変) を変更できるという事実が、違いリストを魅力的なものにしています。では、変更可能な変数だけを持たないのはなぜでしょうか?

アップデート：

diff_append2(OpenList-Hole,L2):-
    Hole=L2.

X=[a,b,c|Ho]-Ho,diff_append2(X,[d,e,f]).
4

1 に答える 1

5

差分リストは、むしろ別の制限を回避するために使用されます: リスト全体をトラバースして最後に「追加」する必要があります (最初の要素へのポインターを持ち、センチネルへのポインターを持たない単一リンクリストを考えてください)。

コード内: リスト[a, b, c]は (伝統的に) ネストされた term.(a, .(b, .(c, [])))であるため、その末尾に a を追加することは、末尾 (中央) の をdに置き換える前に各用語を「剥がす」ことを意味します。したがって、実装するには：[].(d, [])append/3

append([], L, L).
append([H|T], L, [H|R]) :-
    append(T, L, R).

これが伝統的に実装されている方法です。

これは、トピックを非常に広範囲にカバーする別の回答です。

その答えが入っていないのは、リストの最後に追加したい場合に備えて、効率上の理由から、リストを「返す」ライブラリ述語が述語の差分リストバージョンを提供する可能性があるということです。例はread_pending_codes/3and read_pending_chars/3、または の 4 引数バージョンですfindall/4。

DCG は、リストと末尾の 2 つの引数を明示的に渡すことなく、差分リストを操作する便利な方法です。

キューの実装

キューの 3 つの最も基本的な操作: 空のキューの作成、後方へのプッシュ、前方からのポップ:

%% empty_queue(-Queue)
% make an empty queue
empty_queue(queue(0, Q, Q)).

%% queue_head(?Queue, ?Head, ?Queue0)
% Queue, with Head removed, is Queue0
queue_head(queue(s(X), [H|Q], Q0), H, queue(X, Q, Q0)).

%% queue_last(+Queue0, +Last, -Queue)
% Queue0, with Last at its back, is Queue
queue_last(queue(X, Q, [L|Q0]), L, queue(s(X), Q, Q0)).

お気づきのように、queue_head/3前からポップしたり、キューの前にプッシュしたりできます。queue_last/3後ろにプッシュすることしかできません。要素をプッシュすると、キュー内のその前の要素に（一定時間）アクセスできなくなります。

この用語の最初の引数は、queue/3Richard O'Keefe が「幻覚的」変数と呼んでいるもの、つまり、キューにプッシュされたよりも多くの要素をキューからポップすることを防ぐためのものです。上記の述語から最初の引数を除外して、何が起こるかを確認するのは興味深いことです。

?- empty_queue(Q0), queue_head(Q0, H, Q1).
Q0 = queue([H|_G341], [H|_G341]),
Q1 = queue(_G341, [H|_G341]).

失敗する代わりに。

于 2015-08-10T17:39:05.483 に答える