COMP 210 Lab 5: Exam debriefing, Accumulators

Exam debriefing

We'll go over some of the exam problems and solutions.

Accumulators, another example

We'll look at functions to reverse a list.

List reversal examples

  • (Review of in-class example.) Following the template, write reverse-v1 without an accumulator.

    In class, we used a built-in function as a helper. Here, write your own helper function, following the template. This will clarify comparisons with the upcoming accumulator version. 

           #|   Template:

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

       |#

    Sample solution.

  • Write reverse-v2, using an accumulator: add an argument named reverse-so-far, or something like that.

    Sample solution.

  • Step through each versions 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 l, how many steps (approximately) does each version require?

    Sample solution.

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

The standard template approach (non-accumulator) says, "how can we get an answer to our full problem, just using the answers from our sub-parts?".

Sometimes, that info isn't enough: Consider, taking a list of numbers representing bank deposits and withdrawls, 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. Thus an accumulator is necessary. (Another example is the fudge-data from last week's lab: the rest of the datalist may begin with 'fog; the answer depends on data previously seen.

Details, details
An accumulator is not really necessary here. We can do everything without an accumulator that we can with one, and vice versa. But as in this case, sometimes one version is easy and the other is very awkward.

Sometimes, as with reverse and sum, we can write a problem both ways. The primary point is getting solid, clear, correct code; which of the two versions you use isn't so important.

However, as the hand-evaluations show, sometimes 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. Tail-recursion is sometimes called a loop -- it is a special case of recursion in general.

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.