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