52 349 Logic Programming

Chapter 10 - Standard Algorithms & Abstract Data Types

§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

Previous Reading: Essentially Procedural Facilities

§10.1 Sorting Algorithms

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.

§10.1.1 Merge Sort

We can obtain a sorted version of some list by:

  1. splitting it arbitrarily into two sub-lists

  2. recursively sorting the sub-lists

  3. merging the sorted sub-lists

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).

§10.1.2 Quick Sort

Worst case ... disappointing! Average case, good

We can obtain a sorted version of some list by:

  1. randomly selecting some element from it

  2. using that to split the lists into two sub-lists, one of bigger elements and one of smaller elements

  3. recursively sorting the sub-lists

  4. concentrating [appending] the sorted sub-lists, with the splitter in between

Whence for Quick Sort we obtain the top-level 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

  1. that concept is senseless
  2. in our context, it will never arise

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([X|L], M, [X|N]):-
append(L, M, N).

§10.2 Linear A.D.T's - Queues & Stacks

The desirability of solving problems through the use of Abstract Data Types

Of course in Prolog as in many other languages (object-oriented 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 ...

queue(Q, List),
!, fail.
assert((queue(Q, []))).
% Let's not lose any pre-existing data!
queue(Q, []).
% Well, why not? Keep things general!
add(Element, 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):-
!, fail.
remove(Element, Q):-
retract((queue(Q, [Element |List]))),
assert((Queue(Q, List))).
copy(Element, Q):-
!, fail.
copy(Element, Q):-
queue(Q, [Element |_]).

Of course, the six procedures could have been more sophisticatedly named!

We can re-use 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.

§10.3 Binary Trees

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 four-fold 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 sub-tree.
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 sub-tree.
add_leaf(X, Right, Right_1).

Searching something is much like adding to it; so, for our binary search tree, in the intended context in_tree(+,+):

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 sub-tree;
in_tree(X, Left).
in_tree(X, tree(Left, Root, Right)):-
gt(X, Root), % or in the right sub-tree.
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),
show(Left, Inset_2, Step)

This is simply an in-order traverse of the tree, printing each node

Try it in the practical periods!

§10.4 Programming Approach

In a similar way we can handle more complex structures