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.