building blocks:

const fold_left = function (f, base, ls) {

if (ls.size == 0) {

return base;

}

// Write the recursive fold_left call

return fold_left(f, f(base, ls.first()), ls.shift());

};

const map = (g, ls) => fold_left((acc, value) => acc.push(g(value)), List([]), ls);

const filter = (g, ls) => fold_left((acc, value) => g(value) ? acc.push(value) : acc, List([]), ls);

const partition = (g, ls) => List([filter(g, ls), filter(value => !g(value), ls)]);

TO DO DOWN HERE:

/* 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;

/** **/

};

/*

Here are some asserts to check whether your implementations are correct. You

may wish to come up with additional tests and examples.

*/