Close
Register
Close Window

Programming Languages

Chapter 2 Functional Programming

Show Source |    | About   «  2.3. Recurring On Lists That Aren’t Flat   ::   Contents   ::   2.5. Scope, Closures, Higher-order Functions, Static vs. Dynamic Binding  »

2.4. Using Helper Functions with Accumulators

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.

Settings

Proficient Saving... Error 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).

Settings

Proficient Saving... Error 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.

   «  2.3. Recurring On Lists That Aren’t Flat   ::   Contents   ::   2.5. Scope, Closures, Higher-order Functions, Static vs. Dynamic Binding  »

nsf
Close Window