Prolog/差分列表

定義

Prolog 中的差分列表是一個普通的列表，除了它的末尾是一個邏輯變數，與該變數配對。例如

 [a,b,c|E]-E

一個常見的解釋它們為何有用的例子是

 append(I-M, M-O, I-O).

給定此子句，可以查詢

 ?- append([a,b,c|E]-E,  [x,y,z|W]-W,  O).
 E = [x, y, z|W],
 O = [a, b, c, x, y, z|W]-W.

由於這使用了單個統一來追加，因此複雜度為 O(1) 而不是 O(n)。

可以預期一個 DCG 會擴充套件為使用差分列表的普通 Prolog 規則，例如。

?- expand_term(( o --> [a,b,c] ), E).
E = (o(I, O) :- I=[a, b, c|O]).

是一個有效的擴充套件。

較早的示例之一，revappend，可以使用 DCG 編寫

revappend([]) --> [].
revappend([X|Xs]) --> revappend(Xs), [X].