We now briefly describe a valuable technique for programming in
**Prolog**.

Consider the list **[a,b,c|X]**. We
know the structure of the list *up to a point*.

If, at some point, we know that **X** is unbound then we say that we have
an *open list*. We also say (informally) that **X** is a "hole".

Note that we are already familiar with what happens if we unify **X**
with, say, **[d]**:

Here, we started with an?- List=[a,b,c|X], X=[d].List=[a,b,c,d]

This results in a *proper* list (say) --- the normal representation for
a list. We generally think of a list processing procedure as taking a proper
list as input and returning a proper list as output.

Now suppose that we realise that we do not have to represent the idea of a list as a proper list. There is nothing to stop us saying that we will represent a list of things as an open list. That is, we do this instead:

and?- List=[a,b,c|X], X=[d|X1].List=[a,b,c,d|X1]

Now we can think of *open* list processing where we take an open list
as input and return an open list as output.

Of course, if we have an open list as output we can always convert it into a proper list by "filling in" the hole with the empty list (note that, in this case, we could fill in the hole with any proper list) --- as in:

Hang on a minute! We seem to be doing what?- List=[a,b,c|X], X=[d,e,f].List=[a,b,c,d,e,f]

If we had the first list expressed as an open list then all we have to do is
to define a predicate that fills in the hole with the second list. Here is a
very naive (and limited) definition of this sort of **append/3** ---we shall
call it **open_append/2**.

We have turned an open list into a proper list alright but in a limited way because our definition ofopen_append([H1,H2,H3|Hole],L2):-Hole=L2.?- X=[a,b,c|Ho],open_append(X,[d,e,f]).

X=[a,b,c,d,e,f]

If we want to reason about open lists then we often want to say something like "take the open list and fill in the hole with ...". Consequently, we would like to say that a certain term is an open list with such-and-such a hole. This suggests a new representation for the idea of a list --- we represent a list of terms as an open list together with the hole.

This representation is known as a *difference* list --- for a reason
that will become apparent. Such a representation might be that the list of the
terms **a**, **b** and **c** taken in order are represented by two
terms --- ** [a,b,c|Hole]**
and **Hole**. Now let us rewrite **open_append/2** as
**difference_append/3**. We input the open list, the hole and the list to be
appended.

This is better but we now will introduce a notation for difference lists. Since the list we are really interested in is always the open list without the hole we will represent difference lists like this:difference_append(OpenList,Hole,L2):- Hole=L2.?- X=[a,b,c|Ho],difference_append(X,Ho,[d,e,f]).

X=[a,b,c,d,e,f]

Do not worry about the use of the minus operator --- it carries connotations of subtraction but it is just a convenient uninterpreted (in this context) infix operator. We could easily define an operator of our own. Now the above can be rewritten as:[a,b,c,d|Hole] - Hole

Whoops! Now we have returned a difference list but we are only really interested in the open list part --- we want to lop off the hole. We redefinedifference_append(OpenList-Hole,L2):-Hole=L2.?- X=[a,b,c|Ho]-Ho,difference_append(X,[d,e,f]).

X=[a,b,c,d,e,f]-[d,e,f]

We are nearly there now. We have a strange version ofdifference_append(OpenList-Hole,L2,OpenList):-Hole=L2.?- X=[a,b,c|Ho]-Ho,difference_append(X,[d,e,f],Ans).

Ans=[a,b,c,d,e,f]

We could live with this but let us be systematic and produce a version that appends a difference list to a difference list to return a difference list. Here is the first attempt to return a proper list given two difference lists:

Note that we had to change the form of the second argument in order to represent the proper listdifference_append(OpenList1-Hole1,OpenList2-Hole2,OpenList1):-Hole1=OpenList2.?- X=[a,b,c|Ho]-Ho, difference_append(X, [d,e,f|Hole2]-Hole2, Ans).

Ans=[a,b,c,d,e,f|Hole2]

We have returned an open list but we want a difference list. The first list has gained the hole of the second list. All we need to ensure is that we return the hole of the second list. Here we go again!

Now we can recover the proper list we want this way:difference_append(OpenList1-Hole1,OpenList2-Hole2,OpenList1-Hole2):-Hole1=OpenList2.?- X=[a,b,c|Ho]-Ho, difference_append(X, [d,e,f|Hole2]-Hole2, Ans).

Ans=[a,b,c,d,e,f|Hole2] - Hole2

?- X=[a,b,c|Ho]-Ho, difference_append(X, [d,e,f|Hole2]-Hole2, Ans-[]).Ans=[a,b,c,d,e,f]

One more transformation can be made: you will note that all we are saying in
the body of **difference_append/3** is that the hole of the first difference
list has to be the open list of the second difference list.

We now have an extremely neat way of appending two difference lists together to get a difference list. Now, why bother?difference_append(OpenList1-Hole1, Hole1-Hole2, OpenList1-Hole2).

Consider the question about how to add an element to the front of a list.
This is easy because you can, for example, add **X=a** to the list
**Y=[b,c,d]** as in **[X|Y]**. Now
try to write a predicate **add_to_back/3** to take an element and add it to
the end of a list. This does not work.

Not only is this not even a proper list (it does not end inadd_to_back(El,List,Ans):-Ans=[List|El].?- add_to_back(a,[b,c,d], X).

X=[[b,c,d]|a]

This is an expensive procedure. We have to do many computations before getting to the back of the list. We can, however, use difference lists to do this:add_to_back(El,[],[El]).add_to_back(El,[Head|Tail],[Head|NewTail):-add_to_back(El,Tail,NewTail).

This is a cheap computation. Now we could define a version of?- difference_append([b,c,d| Hole1]-Hole1, [a|Hole2]-Hole2, Ans-[]).Ans=[b,c,d,a]

add_to_back(El,OpenList-Hole, Ans):-difference_append(OpenList-Hole, [El|ElHole]-ElHole, Ans-[]).?- add_to_back(a,[b,c,d|Hole]-Hole, Ans).

Ans=[b,c,d,a]

Mon May 24 20:14:48 BST 1999