## Data Structure in Prolog

```Theoretically speaking, Prolog does not have any data structure.
One uses function symbols to represent the intended data
structures.

Example.

Suppose we want to represent lists

()     by     nil
(a)    by     cons(a, nil)
(a b)  by     cons(a, cons(b, nil)),  etc.

Then, we write the program append as

append(nil, X,X).
append(cons(A, L1), L2, cons(A, L3)) :- append(L1, L2, L3).

After the file is loaded, we execute

| ?- append(cons(a1, cons(a2, nil)), cons(b1, nil), Q).

Q = cons(a1,cons(a2,cons(b1,nil))) ?

yes

It's perfectly legal to use any function names you
like to represent lists

append(e, X, X).
append(c(A, L1), L2, c(A, L3)) :- append(L1, L2, L3).
p(W) :- append(c(a1, c(a2, e)), c(b1, e), W).

By this definition, you mean lists are represented as
()     by    e
(a)    by    c(a, e)
(a b)  by    c(a, c(b, e)),  etc.

| ?- append(c(a1, c(a2, e)), c(b1, e), Q).

Q = c(a1,c(a2,c(b1,e))) ?

yes

BUILTIN LIST STRUCTURE:

For the reason of efficiency, there is a builtin list structure.

Lists are represented as
[]           :  empty list
[a, b, c]    :  a list  of three elements
[a, b | L]   :  a list of elements a, b and the rest is L

Under this builtin structure, we can write

append([], X, X).
append([A| L1], L2, [A|L3]) :- append(L1, L2, L3).

p(W) :- append([a1, a2], [b1], W).
q(X,Y) :- append(X,Y,  [a1, a2]).

% execute the queries

| ?- p(A).

A = [a1,a2,b1] ?

yes
| ?- q(A,B).

A = [],
B = [a1,a2] ? ;

A = [a1],
B = [a2] ? ;

A = [a1,a2],
B = [] ? ;

no

```