Download Prolog Programming A First Course

134
Advanced Features
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
Now we can recover the proper list we want this way:
?- 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.
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 [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.
add to back(El,List,Ans):Ans=[List|El].
?- 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,[Head|Tail],[Head|NewTail);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,d|Hole1]-Hole1,[a|Hole2]-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: