Accumulator-Style Functions

When we have decided that an accumulator-style function is necessary, we introduce it in two steps:

Setting-up an accumulator:

First, we must understand what knowledge the accumulator needs to remember about the parameters proper and then how it is to remember it. For example, for the conversion of relative distances to absolute distances, it suffices to accumulate the total distance encountered so far. For the routing problem, we needed the accumulator to remember every node inspected so far. Thus the first accumulator was just a number, the second one a list of nodes.

The best way to discuss the accumulation process is to introduce a template of the accumulator-style function via a local definition and to name the parameters of the function proper differently from those of the auxiliary function.

Let's take a look at the invert example:

;; invert : (listof X) -> (listof X)
;; to construct the reverse of alox 
(define (invert alox0) 
  (local (;; accumulator ... 
          (define (rev alox accumulator)        
            (cond 
              [(empty? alox) ...] 
              [else 
                ... (rev (rest alox)   ) 
                ... ]))) 
    (rev alox0 ...))) 

Here we have a definition of invert with an auxiliary function rev in template form. This auxiliary template has one parameter in addition to those of invert: the accumulating parameter. The box in the recursive application indicates that we need an expression that maintains the accumulation process and that this process depends on the current value of accumulator and (first alox), the value rev is about to forget.

Clearly, invert cannot forget anything, because it only reverses the order of items on the list. Hence we might just wish to accumulate all items that rev encounters. This means

1. that accumulator stands for a list, and
2. that it stands for all those items in alox0 that precede the alox argument of rev.

For the second part of the analysis, it is critical that we can distinguish the original argument, alox0, from the current one, alox.

Now that we know the rough purpose of the accumulator, let's consider what the first value should be and what we should do for the recursion. When we apply rev in the body of the local-expression, it receives alox0, which means that it hasn't encountered any of its items. The initial value for accumulator is empty. When rev recurs, it has just encountered one extra item: (first alox). To remember it, we can cons it onto the current value of accumulator.

Here is the enhanced definition:

;; invert : (listof X) -> (listof X)
;; to construct the reverse of alox 
(define (invert alox0) 
  (local (;; accumulator is the reversed list of all those items 
          ;; on alox0 that precede alox 
          (define (rev alox accumulator)        
            (cond 
              [(empty? alox) ...] 
              [else 
                ... (rev (rest alox) (cons (first alox) accumulator)) 
                ...]))) 
    (rev alox0 empty))) 

A close inspection reveals that accumulator is not just the items on alox0 that precede but a list of these items in reverse order.

Exploiting an accumulator:

Once we have decided what knowledge the accumulator maintains and how it is maintained, we can move to the question of how to exploit this knowledge for our function.

In the case of invert, the answer is almost obvious. If accumulator is the list of all items on alox0 that precede alox in reverse order, then, if alox is empty, accumulator stands for the reverse of alox0. Put differently: if alox is empty, rev's answer is accumulator, and that is the answer we want in both cases:

;; invert : (listof X) -> (listof X)
;; to construct the reverse of alox 
(define (invert alox0) 
  (local (;; accumulator is the reversed list of all those items 
          ;; on alox0 that precede alox 
          (define (rev alox accumulator)        
            (cond 
              [(empty? alox) accumulator] 
              [else 
                (rev (rest alox) (cons (first alox) accumulator))]))) 
    (rev alox0 empty))) 

The key step of this development is the precise description of the role of accumulator. In general, an ACCUMULATOR INVARIANT describes a relationship between the argument proper of the function, the current argument of the auxiliary function, and the accumulator that must always hold when an accumulator-style function is used.