Exercise 12.1

1. We want the following behaviour:

    
   ?- diff_append([a,bX]-X,[c,d,eY]-Y,Answer).
   
   Answer = [a,b,c,d,eY] - Y
   
   

   Here is the solution:

    
   diff_append(List1-Tail1,Tail1-Tail2,List1-Tail2).
   
   

2. We want the following behaviour:

    
    ?- add_at_end(e,[a,b,c,dX]-X,Answer).
   
   Answer = [a,b,c,d,eY] - Y
   
   

   Here is the solution:

    
   add_at_end(X,List-Tail,List-NewTail):-
   
   			Tail=[XNewTail],!.
   
   add_at_end(X,List-[XNewTail],List-NewTail).
   
   

   Note the need to add the cut ( !/0) to prevent unwanted behaviour on backtracking to redo a call to this predicate.

3. We want the following behaviour:

    
   ?- diff_reverse([a,b,cX]-X,Answer).
   
   Answer = [c,b,aY] - Y
   
   

   There are two cases: the first covers the case where we have the difference list equivalent of the empty list.

   The second case covers every other situation: we have to take off the head element, reverse the remaining difference list and then stick the element at the end of the difference list. We use add_at_end/3 that we have already defined.

   Here is a solution:

    
   diff_reverse(X-X,Y-Y):-
   
   		 var(X),!.
   
   diff_reverse([HList]-Tail,Answer):-
   
   			diff_reverse(List-Tail,NewDiffList),
   
   			add_at_end(H,NewDiffList,Answer).
   
   

   Note that, for the first clause, we state that the tail of the input is a variable (via var/1). The use of cut ( !/0) is necessary to stop unwanted behaviour if we ever backtrack to redo this goal.

   Also note that we will get nasty behaviour if the predicate add_at_end/3 has not been defined to prevent unwanted behaviour on backtracking.

4. We want the following behaviour ---assuming that the list is composed of integers or atoms or lists of these. This means that every element is either the empty list, a list or some Prolog term that is atomic. i.e. the term satisfies atomic/1.

    
   ?-  diff_flatten([1,2,[3,4,[5,4,[3],2],1],7X]-X,Ans).
   
   Ans=[1,2,3,4,5,4,3,2,1,7Z]-Z
   
   

   We have three cases: we are going to flatten the empty list by outputting the difference list version of [] --- i.e. X-X. We flatten an `atomic' element other than the empty list by returning a difference list with a single element --- viz [someelementX]-X. The third case is designed to handle the case where the head of the first argument is a list. In this case, we flatten the head, and then flatten the tail.

   Here is a solution:

    
   diff_flatten([HT],X-Y):-
   
   			diff_flatten(H,X-Z),
   
   			diff_flatten(T,Z-Y).
   
   diff_flatten(X,[XT]-T):-
   
   			atomic(X),
   
   			\+(X=[]).
   
   diff_flatten([],X-X).
   
   

   Note how the result of flattening the head is a difference list with a hole. We get the same for flattening the tail and join the lists together by identifying the hole for the flattened head with the open list resulting from flattening the tail.

5. We want the following behaviour:

    
   ?- diff_quicksort([3,1,2X]-X,Ans).
   
   Ans=[1,2,3Z]-Z
   
   

   We should note that the obvious advantage in using difference lists here is in avoiding the various calls to append/3 which can get very expensive. On the other hand, we have to realise that there is an overhead in carrying difference lists around in this form.

   Here is a solution:

    
   diff_quicksort(X-X,Y-Y):-
   
   			var(X).
   
   diff_quicksort([HT]-Hole1,Ans-Hole2):-
   
   			diff_split(H,T-Hole1,SmallDiffList,BigDiffList),
   
   			diff_quicksort(SmallDiffList,Ans-[HZ]),
   
   			diff_quicksort(BigDiffList,Z-Hole2).
   
   diff_split(_,X-X,Y-Y,Z-Z):-
   
   			var(X).
   
   diff_split(X,[YTail]-Hole1,[YSmall]-Hole2,BigDiffList):-
   
   			X > Y,
   
   			diff_split(X,Tail-Hole1,Small-Hole2,BigDiffList).
   
   diff_split(X,[YTail],SmallDiffList,[YBig]-Hole2):-
   
   			X =< Y,
   
   			diff_split(X,Tail,SmallDiffList,Big-Hole2).
   
   

   The correspondence between the difference and proper list versions is close.

   Wherever we have an empty list ( []) we introduce the difference list version ( X-X). We have to be careful to distinguish unrelated empty lists. For example, consider the first clause of quicksort/2 in the notes: quicksort([],[]). The correspondence might suggest diff_quicksort(X-X,X-X). But in this case, there can be very unpleasant consequences as we are forcing certain variables to be identical that might have been distinct up to the point of solving the goal diff_quicksort(A,B). Consequently, we introduce different version of the difference list `empty list' and write diff_quicksort(X-X,Y,Y).

   Note that the `stopping condition' is that we have run out of elements to sort by reaching the `hole'. This means the test is for having encountered a variable. So the procedural reading of the first clause is effectively: return a difference list equivalent to the `empty list' when we find that we have consumed all the non-variable elements from the front of the list. To do this, we use var/1 which takes a Prolog term as input and is true whenever that term is an uninstantiated variable (it can be bound to another uninstantiated variable though).

   The remaining two clauses are structurally very similar to the last two clauses for quicksort/2 as in the notes. The main difference is the loss of the call to append/3 and the means by which we can partially `fill in' the hole of the Small difference list with the result of sorting the Big difference list.

   As for, diff_split/4, we have a very similar situation which we not explain further here.

   What about the efficiency? Is diff_quicksort/2 faster than quicksort/2? And are we comparing like with like? The empirical answer is that quicksort/2 is faster (there are ways of improving the efficiency of the above version of diff_quicksort/2 but they are not sufficient)!

   One reason why this version of diff_quicksort/2 is slower than quicksort/2 is that the former predicate transforms a difference list into a difference list while the latter transforms a proper list to a proper list. An improvement is achieved by writing a version that takes a proper list to a difference list as with:

    
   diff_quicksort_v2([],[]).
   
   diff_quicksort_v2([HT],Ans-Hole2):-
   
   			split(H,T,SmallProperList,BigProperList),
   
   			diff_quicksort_v2(SmallProperList,Ans-[HZ]),
   
   			diff_quicksort_v2(BigProperList,Z-Hole2).
   
   

   Note that we can now use the same split/4 as for quicksort/2.

   The efficiency of this version is now better than the performance of quicksort/2.

6. This one is up to you!