Description
1 Question 1
1. Write an ML function qsort which, given a list of objects l and a comparator function f
(given in curry style, f has type 0a →0 a → bool) outputs a sorted version of l in ascending
order according to f using the classic quicksort algorithm. Note that we are well aware of the
Wikipedia implementation or the other dozen implementations floating on the web. I expect
you to write this on your own! Do not use any basis (library) functions and write every helper
function from first principles. Namely, write
fun qsort l f = …
2. Revisit the previous question, but this time, you cannot define the partition from first principles
(as a recursive function) nor can you use the List.partition basis function. The only thing you
can use is the higher-order function foldr.
fun qsHigh l f = …
3. Write an ML function cross which, given two lists, computes the list of their cross-products.
Namely, given the inputs [1,2,3] and [4,5,6], it computes [(1,4), (1,5), (1,6), (2,4),
(2,5), (2,6), (3,4), (3,5), (3,6)].
fun cross a b = …
4. Revisit the previous question and write an ML function crossHigh that computes the crossproduct in Θ(n ∗ m) (where n and m are the lengths of the input lists) while using exclusively
higher order functions (i.e., nothing you write can be recursive). Feel free to use the append
list function:op@.
fun crossHigh a b = …
5. Finally, revisit the question one last time and produce an implementation that does not use
op@ and only relies on folding.
fun crossFold a b = …
Have fun!
1