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( [ ] )
[ ]

The essence of using the accumulator pattern is to add an extra argument, called an accumulator, to a helper function for the function we are trying to develop. For reverse, we could use a recursive helper function that takes in the input list ns and the list acc that is being built. This is illustrated in the slide show below.

1 / 9 Settings

<<<>>>

When using the accumulator pattern, it is the helper function that does the heavy lifting. The responsibility of the top-level function (here reverse) is to start the accumulator argument at its correct value

1. 3
2. 2
3. 5
4. 8

• var reverse = function (ns) { return reverse_helper(ns, ??? ); }
• var reverse = function (ns) { return reverse_helper(ns, []); }
• var reverse_helper = function (ns,acc) {
• if (fp.isNull(ns))
• return ???
• return acc;
• else
• return reverse_helper(???,
• return reverse_helper(fp.tl(ns),
• ???);
• fp.cons(fp.hd(ns), acc));
• }

hd ns

tl

1. 3

acc is initially [ ]

ns

hd ns

tl

1. 3

acc

hd ns

tl

1. 2
2. 3

acc

hd ns

tl

1. 5
2. 2
3. 3

acc

hd ns

tl

1. 8
2. 5
3. 2
4. 3

acc

Saving...
Server Error
Resubmit

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 below).

1 / 12 Settings

<<<>>>

When using the accumulator pattern, it is the helper function that does the heavy lifting. The responsibility of the top-level function (here split) is to start the accumulator argument at its correct value.

1. 3
2. 5
3. 2
4. 8

• var split = function (pivot,ns) {
• return split_helper(?????);
• return split_helper(pivot, ns, [ ], [ ]);
• };
• var split_helper = function (pivot,ns,smalls,bigs) {
• if (fp.isNull(ns)) {
• return fp.cons(?????);
• return fp.cons(smalls,fp.cons(bigs,[]));
• } else if (fp.isLT(fp.hd(ns), pivot)) {
• return split_helper(pivot, ?????);
• return split_helper(pivot, fp.tl(ns), ?????);
• return split_helper(pivot, fp.tl(ns),
• fp.cons(fp.hd(ns), smalls), ?????)
• fp.cons(fp.hd(ns), smalls), bigs);
• } else {
• return split_helper(pivot, ?????);
• return split_helper(pivot, fp.tl(ns), ????);
• return split_helper(pivot, fp.tl(ns),
• smalls, ?????)
• smalls, fp.cons(fp.hd(ns),bigs));
• }
• };

hd ns

tl

1. 4

pivot

1. 3

smalls initially [ ]

1. 5

bigs initially [ ]

ns

hd ns

tl

1. 3

smalls

hd ns

tl

1. 3

smalls

1. 5

bigs

hd ns

1. 2
2. 3

smalls

1. 5

bigs

hd ns

1. 2
2. 3

smalls

1. 8
2. 5

bigs

hd ns

1. 2
2. 3

smalls

1. 8
2. 5

bigs

Saving...
Server Error
Resubmit

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 Sorting 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.