/* TASK 4 (7.5pts):

Similar to filter we have another function called partition. This function

partitions a list into 2 separate partitions based on a predicate function.

Specifically, partition takes 2 arguments:

1. g - This function decides which partition an element of the list falls into

If the function returns true, then it goes into the left partition,

otherwise it goes into the right partition.

2. ls - This is the list that is to be partitioned.

Some examples of partition are:

partition((x) => x <= 2, List([1,2,3,4])) ------> List([List([1,2]), List([3,4])])

partition((x) => x % 2 == 0, List([1,2,3,4])) ------> List([List([2,4]), List([1,3])])

For this task, your constraint is to write this function using filter. You

are not allowed to use other looping constructs, even fold_left.

*/

const partition = (g, ls) => /** **/ undefined; /** **/

/* TASK 5 (15pts):

Now that we have all the building blocks, our final task is to implement a

naive version of quicksort.

Here's an explanation of how quicksort works:

Given a list to sort, pick an element x from the list as a pivot. Now the

remainder of the list is divided into two partitions, one partition with all

the elements <= x, the other partition with all the elements > x. Now

recursively call the quicksort algorithm on each partition and then combine

the two partitions again (don't forget to put the pivot back in as well!).

The base case for the recursion would be when there's only 1 or 0 elements

in a partition, in which case the partition is returned as is. (The inductive

case is described above.)

Quicksort looks pretty scary in most languages, but with the help of

functional programming, it should only be a few lines of code.

For simplicity, pick the first element of the list as the pivot and the

remaining list as the list to be partitioned.

*/

const quicksort = function(ls) {

if(ls.size <= 1) {

return ls;

}

/** **/

return undefined;

/** **/

};