§10.1  Sorting Algorithms  §10.2  Queues & Stacks  
§10.1.1  Merge Sort  §10.3  Binary Trees  
§10.1.2  Quick Sort  §10.4  Programming Approach 
Chapter 7 introduced lists in Prolog as the fundamental data structure
Details of many of the standard algorithms can be found in the book by Bratko, or in the other standard texts.
For generality, we use the (undefined!) predicate
gt(x, y)
which is true when the instantiated value of x is greater than that of y.
We can obtain a sorted version of some list by:
Merge Sort: an efficient  O(n lgn)  if unstable algorithm.
Following the normal pattern of first giving a name to those things we can't yet do,
merge_sort([], []).
 
% Should be second clause  only relevant once!
 
merge_sort(L, Ans):
 
split(L, A, B),
 
merge_sort(A, A_sort),
 
merge_sort(B, B_sort),
 
merge(A_sort, B_sort, Ans).

Splitting? Compare with append (in §7.1).
With clauses in optimum procedural order,
split([X, Y Rest], [X First], [Y Last]):
 
split(Rest, First, Last).
 
split([X], [X], []).
 
split([], [], []).

Note that, if you allow the middle of these clauses, so
that lists can split unevenly, then you'll also need an additional
first clause for merge_sort, namely
merge_sort([X],[X]).
Why?
Ideally, you also need a cut in that clause, to control backtracking behaviour. Again, why?
And merging? Again, two stopping clauses:
merge([A First], [B Last], [A Ans]):
 
gt(B, A),
 
merge(First, [B Last], Ans).
 
merge([A First], [B Last], [B Ans]):
 
gt(A, B),
 
merge([A First], Last, Ans).
 
merge([], L, L).
 
merge(L, [], L).

Worst case ... disappointing! Average case, good
We can obtain a sorted version of some list by:
Whence for Quick Sort we obtain the toplevel code:
quick_sort([], []).
 
% Which, as before, could and should come second.
 
quick_sort(L, Ans):
 
select(X, L, Rest),
 
split(X, Rest, Small, Big),
 
quick_sort(Small, Small_sort),
 
quick_sort(Big, Big_sort),
 
append(Small_sort, [X Big_sort], Ans).

Note way in which splitting element is put back into the final result!
Select? For simplicity, and very crudely, quite ignoring the randomness of the selection,
select(H, [H Tail], Tail).
Of course, this will fail for an empty list, but
Splitting (around the value of the splitting element)?
split(_, [], [], []).
 
split(Splitter, [Head Tail], [Head Small], Big):
 
gt(Splitter, Head),
 
!,
 
split(Splitter, Tail, Small, Big).
 
split(Splitter, [Head Tail], Small, [Head Big]):
 
split(Splitter, Tail, Small, Big).

Notice how we have made use of clause ordering (and the cut) to excise from the last clause the test gt(Head, Splitter)
.
Appending is as previously given in Chapter 7, namely:
append([], L, L).
 
append([XL], M, [XN]):
 
append(L, M, N).

The desirability of solving problems through the use of Abstract Data Types
Of course in Prolog as in many other languages (objectoriented ones perhaps excepted) we can cheat and only partly implement a definition, but we don't need to
The key idea is that given at the end of Chapter 7, where we in effect adopted a (self) reserved atom to link a name with some particular data set.
Let's implement a queue in this way, using, say,
queue(Q_name, Q_data).
What is a queue? As we know from second year or earlier, a data set which
So ...
new(Q):
 
queue(Q, List),
 
!, fail.
 
new(Q):
 
assert((queue(Q, []))).
 
% Let's not lose any preexisting data!
 
empty(Q):
 
queue(Q, []).
 
full(Q):
 
fail.
 
% Well, why not? Keep things general!
 
add(Element, Q):
 
full(Q),
 
!, fail.
 
% The easy bit  the working part is harder!
 
add(Element, Q):
 
retract((queue(Q, List))),
 
append(List, [Element], New_list),
 
assert((queue(Q, New_list))).
 
% And similarly for remove and copy:
 
remove(Element, Q):
 
empty(Q),
 
!, fail.
 
remove(Element, Q):
 
retract((queue(Q, [Element List]))),
 
assert((Queue(Q, List))).
 
copy(Element, Q):
 
empty(Q),
 
!, fail.
 
copy(Element, Q):
 
queue(Q, [Element _]).

Of course, the six procedures could have been more sophisticatedly named!
We can reuse this code for a stack
 with appropriate renaming
 provided we make one change in add:
append([Element], List, New_list).
Both for queues and for stacks, what we are doing is
The approach is, of course, extensible.
If we are not concerned with data hiding, we may still use the same sort of ideas, but in a simpler way.
For example, we might build a binary tree
tree(Left_subtree, Root, Right_subtree).
Our concept of structures (start of Chapter 7), or knowledge of =.. (from §9.2), gives us confidence that what we have, is a fourfold thing linking together
Trees are fully covered in many of the standard text books (including Bratko)
Building a tree means adding leaves; in the intended context add_leaf(+,+,):
add_leaf(X, nil, tree(nil, X, nil)).
 
% Add to the root of an empty tree.
 
add_leaf(X, tree(Left, X, Right), tree(Left, X, Right)).
 
% If already there, do nothing.
 
add_leaf(X, tree(Left, Root, Right), tree(Left_1, Root, Right)):
 
gt(Root, X),
 % So add to left subtree.
 
add_leaf(X, Left, Left_1).
 
add_leaf(X,tree(Left, Root, Right), tree(Left, Root, Right_1)):
 
gt(X, Root),
 % So add to right subtree.
 
add_leaf(X, Right, Right_1).

Searching something is much like adding to it; so, for our binary search tree, in the intended
in_tree(X, tree(_, X, _)).
 % If X is the data at the root;
 
in_tree(X, tree(Left, Root, Right)):
 
gt(Root, X),
 % or in the left subtree;
 
in_tree(X, Left).
 
in_tree(X, tree(Left, Root, Right)):
 
gt(X, Root),
 % or in the right subtree.
 
in_tree(X, Right).

To display a tree
show(nil, _, _).
 
show(tree(Left, Root, Right), Inset, Step):
 
Inset_2 is (Inset + Step),
 
show(Right, Inset_2, Step),
 
tab(Inset),
 
write(Root),
 
nl,
 
show(Left, Inset_2, Step)

This is simply an inorder traverse of the tree, printing each node
Try it in the practical periods!
In a similar way we can handle more complex structures
The Prolog programming approach is constant:
append([], Ans, Ans)
© Paul Goldfinch 1997  Next Chapter  Return to 52 349 Menu 