CSE 360: Lecture 5

Difference Lists provide access to the tail of a list

The following module shows the technique of difference lists that can be used to concatenate two difference lists in constant time. This is done by having access to the end of the list via a logic variable. Once such a concatentation is made, the variable is bound and can not be use again. We shall see a use of this in the tree sorting module below. 
module difflist.

kind   dlist   type -> type.
type   minus   list A -> list A -> dlist A.
infixr minus   5.

type concat    dlist A -> dlist A -> dlist A -> o.

concat (L minus K) (K minus M) (L minus M).

type d_palindrome   dlist A -> o.

d_palindrome (L minus L).
d_palindrome ((X::L) minus L).
d_palindrome ((X::L) minus K) :- d_palindrome (L minus (X::K)).

type make_dlist   list A -> dlist A -> o.

make_dlist nil (M minus M).
make_dlist (X::L) ((X::K) minus M) :- make_dlist L (K minus M).

type make_list   dlist A -> list A -> o.

make_list (L minus nil) L.

Permutation sorting: it's hard to be more inefficient

One way to sort a list is to use the following generate and test strategy. This is very expensive since a list of n elements has n! permutations, only one of which is sorted. But, it's easy to write such a program. 
type permutation  list A -> list A -> o.
type inorder      list int -> o.
type psort        list int -> list int -> o.

permutation nil nil.
permutation L (H::T) :-
  append V (H::U) L, append V U W, permutation W T.

inorder nil.
inorder (A::nil).
inorder (A::B::Rest) :- A =< B, inorder(B::Rest).

psort L1 L2 :- permutation L1 L2, inorder L2.

Bubble sorting

The following implementation of bubble sort makes a use of the control operator !. 
type bsort        list int -> list int -> o.

bsort L1 L2 :- 
  append Sorted (Big::Small::Rest) L1,
  Big > Small, !,
  append Sorted (Small::Big::Rest) BetterL1,
  bsort BetterL1 L2.
bsort L1 L1.

``Quick'' sorting

Quicksort splits a list into two smaller lists, sorts them recursively, and then merges the results back into one sorted list. This algorithm has good average behavior but can be quadratic in worse case. 
type split        int -> list int -> list int -> list int -> o.
type qsort        list int -> list int -> o.

split X nil nil nil.
split X (A::Rest) (A::S) B :- A =< X, split X Rest S B.
split X (A::Rest) S (A::B) :- A > X,  split X Rest S B.

qsort nil nil.
qsort (First::Rest) Sorted :-
  split First Rest Small Big,
  qsort Small SmallSorted,
  qsort Big BigSorted,
  append SmallSorted (First::BigSorted) Sorted.
The above three sorting predicates can be found in the sorting.mod module.

Using a binary tree to sort a list

One way to sort a list is to first insert all the elements of the list into a labeled binary tree, in which nodes to the left of a node labeled with the integer n are labeled with integers less than or equal to n and nodes to the right are labeled with integers that are greater than n.

Once the elements are inserted, traverse the tree and build out a list of the elements as you visit it. This algorithm also has good average time behavior, but can be quadratic in worse case. The following lines of code are used to introduce labeled binary trees and to insert and lookup items in such trees (lookup is not needed for sorting. 

kind btree    type.
type root     btree.
type bt       int -> btree -> btree -> btree.

type insert   int -> btree -> btree -> o.
type lookup   int -> btree -> o.

insert X root (bt X root root).
insert X (bt D L R) (bt D NewL R) :- X =< D, insert X L NewL.
insert X (bt D L R) (bt D L NewR) :- X > D,  insert X R NewR.

lookup X (bt X L R).
lookup X (bt D L R) :- X =< D, lookup X L.
lookup X (bt D L R) :- X > D,  lookup X R.
Below is the code that builds and then traverses the binary tree to obtain the resulting sorted list. Notice the use of difference list. 
type build     list A -> btree -> o.
type traverse  btree ->  dlist int -> o.
type tsort     list int -> list int -> o.

build nil root.
build (X::L) T1 :- build L T2, insert X T2 T1.

tsort List1 List2 :-
  build List1 T, traverse T (List2 minus nil).

traverse root (L minus L).
traverse (bt D L R) (L1 minus L3) :- 
   traverse L (L1 minus (D::L2)),
   traverse R (L2 minus L3).
The above this sorting predicate can be found in the btree.mod module.
Lecture Directory / Module Directory / CSE360 Syllabus