Next: Prolog Layout Up: Advanced Features Previous: current_op/3

Open Lists and Difference Lists

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

Consider the list [a,b,cX]. 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]:

 
?- List=[a,b,cX], X=[d].

List=[a,b,c,d]

Here, we started with an open list and `filled' in the hole with the structure:

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:

 
?- List=[a,b,cX], X=[dX1].

List=[a,b,c,dX1]

and partially `fill in' the `hole' at the end of the list.

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:

 
?- List=[a,b,cX], X=[d,e,f].

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

Hang on a minute! We seem to be doing what append/3 does here (with mode append(+,+,-))! There is a difference, however, as the first argument is `input' partially instantiated and is `output' wholly instantiated!

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.

 
open_append([H1,H2,H3Hole],L2):-

		 Hole=L2.

?- X=[a,b,cHo],open_append(X,[d,e,f]).

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

We have turned an open list into a proper list alright but in a limited way because our definition of open_append/2 assumes that we have a list with three elements and the hole. We must improve on this.

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

 
difference_append(OpenList,Hole,L2):-

		 Hole=L2.

?- X=[a,b,cHo],difference_append(X,Ho,[d,e,f]).

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

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:

 
[a,b,c,dHole] - Hole

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:

 
difference_append(OpenList-Hole,L2):-

		 Hole=L2.

?- X=[a,b,cHo]-Ho,difference_append(X,[d,e,f]).

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

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 redefine difference_append/2 to be difference_append/3.

 
difference_append(OpenList-Hole,L2,OpenList):-

		 Hole=L2.

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

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

We are nearly there now. We have a strange version of append/3 which takes a difference list as its first argument, a proper list as its second argument and returns a proper list.

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:

 
difference_append(OpenList1-Hole1,OpenList2-Hole2,OpenList1):-

		 Hole1=OpenList2.

?- X=[a,b,cHo]-Ho,difference_append(X,[d,e,fHole2]-Hole2,Ans).

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

Note that we had to change the form of the second argument in order to represent the proper list [d,e,f] as a difference list.

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!

 
difference_append(OpenList1-Hole1,OpenList2-Hole2,OpenList1-Hole2):-

		 Hole1=OpenList2.

?- X=[a,b,cHo]-Ho,difference_append(X,[d,e,fHole2]-Hole2,Ans).

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

Now we can recover the proper list we want this way:

 
?- X=[a,b,cHo]-Ho,difference_append(X,[d,e,fHole2]-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.

 
difference_append(OpenList1-Hole1,Hole1-Hole2,OpenList1-Hole2).

We now have an extremely neat way of appending two difference lists together to get a difference list. Now, why bother?

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

 
add_to_back(El,List,Ans):-

			Ans=[ListEl].

?- add_to_back(a,[b,c,d],X).

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

Not only is this not even a proper list (it does not end in []) but it is not equal to [b,c,d,a]! What we have to do is something like:

 
add_to_back(El,[],[El]).

add_to_back(El,[HeadTail],[HeadNewTail);-

			add_to_back(El,Tail,NewTail).

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:

 
?- difference_append([b,c,dHole1]-Hole1,[aHole2]-Hole2,Ans-[]).

Ans=[b,c,d,a]

This is a cheap computation. Now we could define a version of add_to_back/3 for difference lists:

 
add_to_back(El,OpenList-Hole,Ans):-

			difference_append(OpenList-Hole,[ElElHole]-ElHole,Ans-[]).

?- add_to_back(a,[b,c,dHole]-Hole,Ans).

Ans=[b,c,d,a]

Next: Prolog Layout Up: Advanced Features Previous: current_op/3

Paul Brna
Mon May 24 20:14:48 BST 1999