/*

In this exercise you will implement quicksort in JavaScript, using high-order

functions. We have provided some scaffolding and broke the problem into

several different tasks.

*/

/* TASK 1 (10pts):

Your first task is to write the definition of fold_left. This function is

sometimes called reduce; you may remember it from its brief mention in class

or its popularization by MapReduce.

This function takes in 3 arguments as follows:

1. f - This is the folding function

2. base - This is the base value of the accumulator

3. ls - This is the list which is to be folded over

The goal of fold_left is to fold a list into a single value.

It starts from the beginning (left-side) of the list and applies the folding

function with the base value and the 1st element of the list. The value

returned by applying this function is then used as the new base value for

the folding function and the next element of the list is used as the other

parameter. This is done until the list is exhausted, the final accumulated

value being the return value.

fold_left is implemented recursively, applying the folding function on the

accumulator and the first element each time, and then recursively passing the

new accumulator and the remaining list. The accumulated result is returned

when the list is empty.

For example, let's take a look at a function that uses fold_left.

*/

const sumList = (ls) => fold_left((acc, x) => acc + x, 0, ls);

/*

The sumList function takes a list (`ls`) and returns the sum of the elements

in the list.

The inline folding function takes the current accumulator (`acc`) and next

element in the list (`x`) and simply returns their sum.

The base (initial accumulator) value when summing a list starts as 0.

The correct behavior of this function, when expanded into call stacks, looks

like this:

fold_left((+), 0, List([1,2,3]))

fold_left((+), 1, List([2,3]))

fold_left((+), 3, List([3]))

fold_left((+), 6, List([]))

6

6

6

6

6

Note: The list that's passed into fold_left (and all subsequent functions) is

of type immutable.List. You will learn more about the benefits of immutability

in future lectures. For this assignment, you should look at the following

docs:

https://facebook.github.io/immutable-js/docs/#/List

Some useful List functions for this exercise in particular are:

size()

first()

last()

push()

pop()

unshift()

shift()

get()

slice()

concat()

You can read more about them in the link above.

Implement fold_left below following the above description and example.

*/

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

if (ls.size == 0) {

return base;

}

// Write the recursive fold_left call

return /** **/ undefined; /** **/

};

/*

In this exercise you will implement quicksort in JavaScript, using high-order

functions. We have provided some scaffolding and broke the problem into

several different tasks.

*/

/* TASK 1 (10pts):

Your first task is to write the definition of fold_left. This function is

sometimes called reduce; you may remember it from its brief mention in class

or its popularization by MapReduce.

This function takes in 3 arguments as follows:

1. f - This is the folding function

2. base - This is the base value of the accumulator

3. ls - This is the list which is to be folded over

The goal of fold_left is to fold a list into a single value.

It starts from the beginning (left-side) of the list and applies the folding

function with the base value and the 1st element of the list. The value

returned by applying this function is then used as the new base value for

the folding function and the next element of the list is used as the other

parameter. This is done until the list is exhausted, the final accumulated

value being the return value.

fold_left is implemented recursively, applying the folding function on the

accumulator and the first element each time, and then recursively passing the

new accumulator and the remaining list. The accumulated result is returned

when the list is empty.

For example, let's take a look at a function that uses fold_left.

*/

const sumList = (ls) => fold_left((acc, x) => acc + x, 0, ls);

/*

The sumList function takes a list (`ls`) and returns the sum of the elements

in the list.

The inline folding function takes the current accumulator (`acc`) and next

element in the list (`x`) and simply returns their sum.

The base (initial accumulator) value when summing a list starts as 0.

The correct behavior of this function, when expanded into call stacks, looks

like this:

fold_left((+), 0, List([1,2,3]))

fold_left((+), 1, List([2,3]))

fold_left((+), 3, List([3]))

fold_left((+), 6, List([]))

6

6

6

6

6

Note: The list that's passed into fold_left (and all subsequent functions) is

of type immutable.List. You will learn more about the benefits of immutability

in future lectures. For this assignment, you should look at the following

docs:

https://facebook.github.io/immutable-js/docs/#/List

Some useful List functions for this exercise in particular are:

size()

first()

last()

push()

pop()

unshift()

shift()

get()

slice()

concat()

You can read more about them in the link above.

Implement fold_left below following the above description and example.

*/

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

if (ls.size == 0) {

return base;

}

// Write the recursive fold_left call

return /** **/ undefined; /** **/

};