## 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

### §10.1 Sorting Algorithms

Chapter 7 introduced lists in Prolog as the fundamental data structure

• and it emphasised recursive techniques

Details of many of the standard algorithms can be found in the book by Bratko, or in the other standard texts.

• but to emphasise the basic Prolog points we look at two sorting algorithms studied in second year (and in the class 52 344)

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

• but likely to be hampered by the over simple selection we use here!

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

• collections of data and of the operations permitted on them

• doesn't alter as we change the programming paradigm

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

• although the flexibility of Prolog is such that we do need
to exercise self-discipline

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

• can be initialised to be empty
• can be empty or full
• if not full can have a data element added at the rear
• if not empty can have its first element removed or copied

So ...

 `new(Q):-` `queue(Q, List),` `!, fail.` `new(Q):-` `assert((queue(Q, []))).` `% Let's not lose any pre-existing 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 re-use this code for a stack

- with appropriate renaming

• say, new_stack for new

• and preferably a "reserved" stack/2

- provided we make one change in add:

• the append line becomes

`append([Element], List, New_list).`

Both for queues and for stacks, what we are doing is

• using queue/2 (or stack/2) to associate a name uniquely with some data

• hiding from the user the way we have implemented the data structure

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

• by defining a "reserved" atom, say nil, to represent an empty tree

• and for generality some function tree/3
`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

• the concept of a binary tree; and
• its three sub-components (root and two sub-trees).

Trees are fully covered in many of the standard text books (including Bratko)

• but let's look at building, searching and displaying them

• in the context of a binary search tree

 `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

• we can of course use write/1

• but that generates an unpleasant tangle of nodes and brackets
(remember the parser-like 52 222 example?)

• or we can use an algorithm to show the shape of the tree,
by rotating it 90° to the left.

 `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 in-order traverse of the tree, printing each node

• but arranged so that sub-trees are printed "Step" spaces to the right of their roots

• and so that the root of the tree is printed "Inset" spaces from the print margin

Try it in the practical periods!

### §10.4 Programming Approach

In a similar way we can handle more complex structures

• for example, graphs have a list of vertices together with a series of edge/2 structures

• hiding the data as may be appropriate

The Prolog programming approach is constant:

• select an appropriate, simple representation

• think through all possible situations

• normally defined recursively
• with relevant stopping conditions

• translate into Prolog style

• for example, `append([], Ans, Ans)`
• using repeated variables to match pattern

• re-think your code from a procedural viewpoint.