2.4.1. Using helpers to write reverse and split functions¶

How would you design a reverse function that takes in a list of integers and returns a list containing the same elements as the input list but in reverse order?

> reverse( [1,2,3] )   // we could start with [ ] and insert 1 into it to get [ 1 ]
[ 3, 2, 1 ]            // then insert 2 into [ 1 ] to get [ 2, 1 ]
                       // then insert 3 into [ 2, 1 ] to get [ 3, 2, 1 ]
> reverse( [ ] )
[ ]

With an accumulator we could use a recursive helper function that takes in the input list ns*and the list *a being built and returns ...

var reverse_helper = function (ns, a) {
                        if (fp.isNull(ns)) {
                             return ???
                        } else {
                             ??????????
                        }
}

Then we would call this helper function with a reverse function that acted as a front-end, passing in the initial value for a. The extra parameter in the helper function is called an accumulator.

var reverse = function (ns) { return reverse_helper(ns, ??? ); }

As another example of using an accumulator, consider how you would design a split function that takes in an integer $n$ and a list $ns$ of integers and returns two lists, the first one of which contains all of the elements of $ns$ that are smaller than $n$ and the second one contains the remaining elements of $ns$?

> split(5, [1,9,2,8,3,7])
[ [ 3, 2, 1 ], [ 7, 8, 9 ] ]
> split(5,[ ])
[ [ ] [ ] ]

We call the first argument of split the pivot because of a famous algorithm that uses split (see the second review problem).

var split_helper = function (pivot,ns,smalls,bigs) {

            ??????
}


var split = function (pivot,ns) {
    return split_helper(pivot, ns, [ ], [ ]);
}

The first review problem will test your understanding of split and another function called join, which is also developed using an accumulator.

2.4.2. Using the split function to develop a sort function¶

This problem will have you use the split function to implement an efficient sorting algorithm.

2.4.3. Additional Practice with the Accumulator Pattern¶

This problem will give you a lot more practice with the accumulator pattern. It is a randomized problem. You have to solve it three times in a row.