Assignment 2
Distributed: Nov 12 - Solutions Emailed in: Nov 20/23 - Resolved: Nov 23/25

Information Systems for Business Applications, Harold Boley, Winter 1998

Given is the following mixed functional-relational definition of the well-known quicksort function qsort with subrelation partition for sorting a tuple of numbers.
qsort([]) :& [].
qsort([X|Y]) :- partition(X,Y,Sm,Gr) &    % results bound to Sm and Gr

partition(X,[Y|Z],[Y|Sm],Gr) :-
   <(Y,X),  partition(X,Z,Sm,Gr).
partition(X,[Y|Z],Sm,[Y|Gr]) :-
   <(X,Y),  partition(X,Z,Sm,Gr).
partition(X,[X|Z],Sm,Gr) :- partition(X,Z,Sm,Gr).   % remove duplicates

appfun([],L) :& L.                     % appfun([],[2]) = [2]
appfun([H|R],L) :& tup(H|appfun(R,L)). % appfun([1],[2]) = tup(1|appfun([],[2]))

Paste this into a file qsort-fr.rfp and consult it into RelFun. Perform trace qsort and also trace partition, and then call qsort([4,1,3,1,2]) and do a more. Note that qsort is (ground-)deterministic - in spite of the more general ":&"-syntax - and that the call pattern for partition is


a) Transcribe the above definition into a purely relational qsort-r.rfp such that a relation call of the form


in Input expects the given tuple and binds Output to the sorted tuple. Test it for calls (some of which being `counter examples') like


and explain possibly surprising results (error messages?).

b) Transcribe the original definition into a purely functional qsort-f.rfp such that a function call of the form


in Input1 expects the comparison element, in Input2 expects the tuple to be partitioned, and with these returns the value

where Output1 is the result tuple of smaller elements and Output2 is the result tuple of larger elements. First test it for calls like
seq[Sm,Gr] .= partition(3,[1,4,2])

Then test qsort for calls like


with tracer on for partition and/or qsort.

c) Discuss possible advantages and disadvantages of the functional-relational, purely relational, and purely functional versions.

d) Transcribe the original definition into a higher-order functional-relational qsort-hofr.rfp which abstracts from the binary arithmetical comparison relation, i.e. replace the relation constant < by a relation variable Cr so that a function call of the form


returns the Input tuple sorted w.r.t. the value of Cr. Test this parameterized qsort for calls like


with a yet-to-be-defined comparison relation second< that applies < to the second tuple elements. Use a suitable parameterization of qsort for sorting the tuple of solution tuples returned by the call tupof(order(N,time[1998,11,D])) - with order defined in opstup.bat - according to the amount of peaches (optionally make use of the th1 built-in).