COMP 210 Lab 5: More Accumulators

First, let's return to an in-class example, reversing a list.

List reversal examples

  • (Review of in-class example.) Write reverse-acc with an accumulator representing the reversal of the elements seen so far. 

           #|   Template:

       ;; list-fun: list ... --> ...
       ;;
       (define (list-fun a-list acc)
         (cond [(empty? a-list) ...acc...]
               [(cons?  a-list) (list-fun (rest a-list)
                                          ...(first a-list)...acc...]))

       |#

  • Following the template, write reverse-noacc without an accumulator.

    Hint: You'll want a helper function. That helper should also be a recursive function without an accumulator. This will clarify comparisons with the upcoming accumulator version. 

           #|   Template:

       ;; list-fun: list --> ...
       ;;
       (define (list-fun a-list)
         (cond [(empty? a-list) ...]
               [(cons?  a-list) ...(first a-list)...
                                ...(list-fun (rest a-list))...]))

       |#

  • Step through each version on some input. Pay attention to the computations just before the recursive calls. Also, pay attention to how many steps are in each evaluation. To reverse a list of length N, how many steps (approximately) does each version require?

  • To discuss: In this particular case, is either of these versions preferable? Why or why not?

Sample solutions.

As in this example, different algorithms can lead to fundamentally faster ways of doing a task. We'll talk more about this later. Always keep in mind that it's more important to write a function so that it is clear, correct, and maintainable, than one that is faster but more confusing. Studies show that even experienced professional programmers aren't good at predicting where bottlenecks occur in code. First write your code correctly; if you find it runs too slowly, you can use DrScheme's profiler and find out which functions you want to focus on, to optimize later.

Let's contrast those two examples to the following.

Adding 1 to each number in a list examples

  • Write a function add1-to-each-noacc without an accumulator. By now, this should be really easy. 

           (add1-to-each-noacc (list 3 7 1))    returns    (list 4 8 2)

  • Similarly, write add1-to-each-acc with an accumulator. Do not reverse any lists.

  • To discuss: In this particular case, is either of these versions preferable? Why or why not?

Neither approach is always better. As with summing the elements in a list, for some problems, it doesn't really matter much. On the other hand, as in the above problems, often the choice matters significantly. One of the approaches might be significantly easier and more efficient.

It turns out that we can do everything without an accumulator that we can with one, and vice versa, the difference can be surprisingly awkward. For example, consider taking a list of numbers representing bank deposits andwithdrawls, and asking if the balance ever goes negative. Our input might be (list +100 -21.50 -41.50 +200). Unfortunately, looking at just the rest of this list doesn't help you build the answer to the full problem; it really depends on the running balance-so-far.

However, as the hand-evaluations show, accumulator-style functions yield tail-recursive functions -- the answer to the recursive call is the answer to the entire question. This means that you don't build up a whole waiting list of pending function calls. This is also known as a loop -- looping is just a special case of recursion.

On the other hand, with accumulator-style functions, you must decide what is the accumulator accumulating? So far, we've often answered this step for you, but it is generally the hardest part of using accumulators. Sometimes, answering this question can be very difficult.

Reverse- and forward-accumulation are not mutually exclusive. The two ideas can be combined, as you've seen in a couple in-class examples. The following is also an example of this.

List sum examples

We've had a bunch of examples of summing things. Here's another variant that is very useful, not only pedagogically, but also for real applications.

Develop a function prefix-sums that returns a list of all the partial sums of elements in the list. 

  (prefix-sums (list 1 8 7 3))      returns     (list 1 9 16 19)
  (prefix-sums (list 1 1 1 1))      returns     (list 1 2 3 4)
Sample solution.
Pascal's Triangle examples

If you have time, here's a problem somewhat similar to the previous one that you may be familiar with already, Pascal's Triangle. (For lots of neat info on why it's interesting, see here or here.) As it is usually drawn, Pascal's Triangle looks like this:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
...

  • Develop a function that takes one row and produces most of the next row of Pascal's Triangle. 

           Input: (list 1)           Output: (list 1)
       Input: (list 1 3 3 1)     Output: (list 1 4 6 4)

    This should be similar to prefix-sums.

  • Use or modify this function to produce all of the next row: 

           Input: (list 1)           Output: (list 1 1)
       Input: (list 1 3 3 1)     Output: (list 1 4 6 4 1)

  • Create a function that take a number n and returns the nth row of Pascal's Triangle.

  • For a challenge... Create a function that computes the first n triangular numbers, as highlighted below.

    1
    1 1
    1 2 1
    1 3 3 1
    1 4 6 4 1
    1 5 10 10 5 1
    1 6 15 20 15 6 1
    ...