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(,) =  appfun([H|R],L) :& tup(H|appfun(R,L)). % appfun(,) = tup(1|appfun(,))
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
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
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
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
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).