Comp 210 Lab 8: Accumulators

Accumulators,

Accumulators

The Big Picture (review)

In-class, we saw three examples for accumulators:

The idea was that we use an extra argument in our function(s), called the accumulator, which "accumulates" some information about the problem, often the eventual result. In the first, it was the sum of the numbers visited so far. The the second, it was the reverse of the front part of the list. In the third, it was the sum of the number visited so far.

When do we use accumulators? It's hard to give any firm rules, and it's best to learn from examples. In general, you should always try to solve a problem without accumulators (using plain structural or generative recursion), and only add accumulators when it (i) simplifies the structure of the solution, (ii) fundamentally improves the asymptotic running time of the program, or (iii) converts a program to tail-recursive form.

In the first two examples from class, we used an accumulator to reduce the asymptotic complexity of the solution from O(n^2) to O(n). In the third example, we converted the program to tail-recursive form, which reduces the space complexity of the computation from O(n) to O(1) (constant space). Note: a program P runs in time (or uses space) O(f(n)) for some function f, if the running time (space usage) on inputs of size n, for suffciently large n, is bounded by C*f(n) for some constant C. The "sufficiently large n" qualification provides exceptions for values of n below some threshold N. For example, say that we define the size of a list as the length of the list and we have written a linear version of the reverse function. The reverse function on the empty list runs very fast but it does not run in zero time, which is what our definition would require if we did not allow a finite number of exceptions. Obviously any function that runs time O(n) also technically runs in time O(n^2) and O(2^n). By convention, we use the best (smallest) possible function f when stating asymptotic complexity. If a program runs in linear time (O(n)), it is misleading to say that is runs in quadratic time (O(n^2)).

Let's use accumulators in a some additional examples.

Maximum of a list of numbers

By now, we certainly know how to find the maximum of a non-empty list of numbers. Why might we prefer to use an accumulator for this problem? The obvious structural recursion solution is not tail-recursive, but the accumulator version is.

Typically, the accumulator represents whatever you will give as the final answer, or at least as much of it that you have calculated so far.

The header and contract should account for the accumulator. Your purpose should also describe the accumulator. 

     ; max-list-acc : (list-of num) num -> num
     ;   returns the maximum of the numbers in alon which must be non-empty, plus
     ;   max-so-far, which holds the maximum of numbers preceding alon
     (define (max-list-acc alon max-so-far) ...)

To do: Write the function. You should still use the appropriate structural recursion template. (The accumulator versions of structural recursive programs are structually recursive also; they simply take an extra argument.)

Q: What should the initial call be to the max-list-acc, i.e., what should the initial value of the accumulator be?

The initial accumulator value is typically the same value that you would've used as the return value for the non-accumulator version's base case.

Since we usually don't want other people using our function to have to know about the accumulator, let's create a version that calls this function with the appropriate initial accumulator. 

     ; max-list : list-of-num -> num
     ;   returns the maximum of the numbers in alon which must be non-empty
     (define (max-list alon)
        ...)
To do: Write this function.

Note how it has the same contract and purpose as our standard non-accumulator version of the function from earlier in the class. Anyone using this function doesn't care how it's implemented, just as long as it lives up to its contract and purpose.

Of course, as we already know, it is even better to hide the accumulator version from any prying eyes: 

     (define (max-list alon)
        (local [(define (max-list-acc alon max-so-far)
                   ...)]
           ...))

For brevity, we skipped the step of making examples. Now that we see how the accumulator is supposed to be used, go back and test the accumulator version. (Test the version before it was hidden inside a local.)

As a programmer, you might prefer the original non-accumulator version of max. It is slightly easier to understand. But the accumlator version is much more space efficient.

foldl

Recall our previous definition 

     (define (reverse aloa) 
        (foldl cons empty aloa))
foldl is very similar to the accumulator-based reverse.

To do: Recall the equational definition of foldl: 

     (foldl f base (list x1 x2 ... xN)) = (f xN ... (f x2 (f x1 base))...)
Write foldl using structural recursion and an accumulator.

split/split-list

Recall the function split (which is not accepted as a function name in some versions of DrScheme because it is keyword) used as a helper for mergesort in the last homework assignment.

To do: Write a definition for split that uses accumluators to form the "left" and "right" parts of the input list. Call your function split-list if your version of DrScheme does not accept the name split.

flatten

Recall the function flatten from Homework 4 that flattens a list-of-list-or-symbol to a (list-of symbol).

To do: Write a definition for flatten that uses an accumulator to form the flattened list.

dup-names

Recall the function dup-names from Homework 5 that finds the duplicated names in a parent-based family tree.

To do: Write a definition for dup-names that uses an accumulator to record the names that been scanned so far.

To do: Write a definition for dup-names that uses a second accumulator to hold the answer and uses this accumlator to avoid including duplicates in the answer (when a name appears more than twice).