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

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

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