THE FOLLOWING QUESTION IS IN OCAML

In SICP, the authors introduce the filter higher-order function. Translated into OCaml, that definition would be:

let rec filter predicate sequence = match sequence with | [] -> [] | h :: t when predicate h -> h :: filter predicate t | _ :: t -> filter predicate t 

where predicate is a function of one argument returning a bool, and sequence is a list. We will use this in this section. (In the OCaml libraries, this function is available as List.filter).

1. Quicksort

[4] (20 minutes)

Implement a quicksort function that sorts a list of integers in ascending order, returning the new (sorted) list. The quicksort function works like this:

If the list is empty, return the empty list.

Otherwise, the first element in the list is called the pivot. Use it to create a list of all the elements in the original list which are smaller than the pivot (using the filter function), and another list of elements in the original list which are equal to or larger than the pivot (not including the pivot itself). Then recursively quicksort those two lists and assemble the complete list using the OCaml list append operator (@).

To make this function extra-general, instead of using the < operator to define whether an element is smaller than another, abstract it around a comparison function cmp which takes two values and returns a bool. We saw examples of this in lecture 9. Make the comparison function the first argument of quicksort. Using (<) as this argument makes the function sort in ascending order (the most usual way of sorting).

Examples

# quicksort (<) [] ;; - : 'a list = [] # quicksort (<) [1] ;; - : int list = [1] # quicksort (<) [1; 2; 3; 4; 5] ;; - : int list = [1; 2; 3; 4; 5] # quicksort (<) [5; 4; 3; 2; 1; 2; 3; 4; 5] ;; - : int list = [1; 2; 2; 3; 3; 4; 4; 5; 5] # quicksort (>) [5; 4; 3; 2; 1; 2; 3; 4; 5] ;; - : int list = [5; 5; 4; 4; 3; 3; 2; 2; 1] 

Our solution is 7 lines long.

2. Quicksorts recursion class

[1] (10 minutes)

Explain (in an OCaml comment) why the quicksort function is an instance of generative recursion and not structural recursion.