Last modified on 9 February 2013, at 19:54

# Prolog/Difference Lists

previous: Reading and Writing code next: Definite Clause Grammars

## DefinitionEdit

A Difference list in Prolog is a normal list except the very end of it is a logic variable, paired with that variable. For example:

``` [a,b,c|E]-E
```

## DemonstrationEdit

A common example to explain why they are useful is:

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

Given this clause one can query:

``` ?- 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.
```

Since this uses a single unification to append you have O(1) instead of O(n) complexity.

## Internal to Definite Clause GrammarsEdit

You can expect a DCG to expand into normal Prolog rules which use difference lists, for example.

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

is a valid expansion.

## ExamplesEdit

One of the earlier examples, revappend, can be written using DCG:

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