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
   appfun(qsort(Sm),tup(X|qsort(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
partition(X,[],[],[]).

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

partition(Input1,Input2,Output1,Output2)

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

qsort(Input,Output)

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

qsort([3,1,4,2],Sorted)
qsort([3,1,4,2,3],Sorted)
qsort(Unsorted,[2,1,3,4])
qsort(Unsorted,[1,2,3,4])

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

partition(Input1,Input2)

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

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

Then test qsort for calls like

qsort([3,1,4,2])

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

qsort[Cr](Input)

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

qsort[<]([3,1,4,2])
qsort[string<]([three,one,four,two])
qsort[second<]([[mannheim,10.50],
                [freiburg,9.15],
                [kaiserslautern,10.12]])

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