Page History

...

The fundamental notion of an accumulator algorithm is that the data needed for a particular calculation is spread throughout a data structure, thus necessitating a traversal process that "accumulates" the answer as the algorithm "travels" from one data element to the next.  Note that the notion of "accumulation" here is at its most general and does not necessarily mean an additive or multiplicative process--it could be one where each element is kept or discarded, as a filtering algorithm would do.

"Reverse Accumulation"

Let's look at an example of what the HTDP book calls a "natural" recursion algorithm:

...

;; return the largest positive number in a list of numbers or zero if there are no positive values.
(define (get_largest_pos lon)
   (cond 
       [(empty? lon) 0]
       [(cons? lon) 
          (local
               [(define acc (get_largest_pos (rest lon)))]
               (if (> (first lon) acc) (first lon) acc))]))   

Here we can see that the accumulated value is just the largest value from the rest of the list at any given point.

...

"Forward Accumulation"

A general mantra that we have about moving data during an algorithm's execution is to say that we are "moving data from where it is, to where it can be processed".   

In a reverse accumulation algorithm on a list, we recur all the way to the empty list before we start accumulating our result because that is the only place where the return value is unequivocally defined.  The result is thus accumulated in the "reverse" direction as we slowly exit the recursion layer by layer.

If we can accumulate results by moving data from the rear of the list towards the front of the list, can we also accumulate a result by moving data the other direction, namely from the front of the list towards the rear?   But of course!

Let's look at how we would sum a list of numbers using "forward accumulation":

(define (sum_fwd lon)
  (cond
    [(empty? lon) 0]
    [(cons? lon)
     (local
       [(define (helper acc aLon)
          (cond
            [(empty? aLon) acc]
            [(cons? aLon) (helper (+ (first aLon) acc) (rest aLon))]))]
       (helper (first lon) (rest lon)))]))   

Notice, first of all, that the function requires a helper function? Why? Because the only way to pass data forward in the list is to use an input parameter, but since forward accumulation is an implementation detail of the function, there are no (and should not be any) provisions in the input parameters of the original function, sum_fwd, for passing the accumulated result. Thus a helper function with an extra input parameter is needed, to handle the accumulating value.

 (more coming...)

 Forward accumulation