On this page:
7.1 Brute Force
7.2 Accumulator Functions
7.3 Designing with Accumulators

7 Accumulators

Some problems seem to require convoluted solutions at first glance. Here is one of them:

Sample Problem Someone measured the relative distances between a series of points. What is needed, however, is the list of absolute distances of each point to the first one.

The idea seem simple. Here is a sequence of relative distances:

  1.7    3.2   2.1

It means the first point is 1.7m from the starting point, the second point is 3.2m from the first point, and the third point is 2.1m from the second point. Clearly, the following is the series of absolute distances:

  1.7    4.9   7.0

All you have to get to do to get from the first to the second is add up the distances as you go along the series.

7.1 Brute Force

Let us solve this problem following the design recipe:
  1. the data definition:
    (define-language Lon
      (l (n ...))
      (n number))
    The natural representation for sequences of numbers are lists of numbers. Here are the examples from above in this language:
    (define example1 (term (1.7 3.2 2.1)))
    (define example2 (term (1.7 4.9 7.0)))

  2. purpose statement and contract

    ; turn a list of relative distances into a list of absolute distances

  3. we already have one example and it is easy to make up others:
    ; given example1, expect back example2
    ; given (term (1 1 1)), expect back (term (1 2 3))

  4. the template
    (define-metafunction Lon
      absolute : l -> l
      [(absolute ()) .....]
      [(absolute (n_head n_rest ...))
       ..... n_head ..... (absolute (n_rest ...)) .....])

  5. time to code:
    (define-metafunction Lon
      absolute : l -> l
      [(absolute ()) ()]
      [(absolute (n_head n_rest ...))
       ,(cons (term n_head) (term (add-to-all n_head (absolute (n_rest ...)))))])
    Question is what is this add-to-all function doing here?

    Here is the problem. We know that n_head is first element of the given list and we know what (absolute (n_rest ...)) computes the absolute distances for the rest of the list. But, these absolute distances do not take into account n_head because a mathematical function knows nothing but its inputs, and n_head is not an input to this recursive calls.

    At this point you should say “no problem” because it is straightforward to define a function that adds n_head to all the elements of the list. We call this function add-to-all and we provide its definition (in the form of a homework solution) without going through the whole design recipe:
    ; add n to all numbers on l
    (define-metafunction Lon
      add-to-all : n l -> l
      [(add-to-all n ()) ()]
      [(add-to-all n (n_head n_rest ...))
       ,(cons (+ (term n) (term n_head)) (term (add-to-all n (n_rest ...))))])
     
    (test-equal (term (add-to-all 1 (1 1))) (term (2 3)))
    If you have any doubts about this definition, work through the design steps.

    For the ,(cons ... ...) part, recall that unquote takes the calculation back to Racket. If you look up cons’s documentation, you will find out that it constructs a list from a given element and another list. Thus, ,(cons 1 (term (2 3))) yields (term (1 2 3)).

  6. tests
    (test-equal (term (absolute (1 1 1)))
                (term (1 2 3)))
    (test-equal (term (absolute ,example1))
                (term (1.7 ,(+ 1.7 3.2) ,(+ 1.7 3.2 2.1))))
    Since the tests succeed, we know that add-to-all works, too. If not, we would equip the latter with tests derived from these just to make sure the helper function works before we debug anything else.

The problem with this solution is twofold. First, we should need two functions that traverse entire lists to transform a list of relative distances into a list of absolute distances. Second, if you recall your algorithms, you know that the nesting of traversals requires O(n2) iterations over a list of n elements. As mentioned above, the naive solution is to just keep a running sum.

7.2 Accumulator Functions

Except that this solution idea doesn’t fit into the picture with the obvious purpose statement and contract for this function. Recall that the problem calls for a function that consumes a sequence of numbers and that produces one, so the purpose statement and the contract are correct:
; turn a list of relative distances into a list of absolute distances
(define-metafunction Lon
  absolute : l -> l)
Keeping a running sum, however, calls for an additional parameter, which is not what the problem statement called for:
; turn a list of relative distances into a list of absolute distances
; relative to the given starting distance n
(define-metafunction Lon
  running-sum : l n -> l)

To resolve this seeming contradiction, we introduce the latter as an auxiliary function to which absolute immediately dispatches with a properly initialized second argument:
; turn a list of relative distances into a list of absolute distances
(define-metafunction Lon
  absolute : l -> l
  [(absolute l_0) (absolute-accu l_0 0)])
From a mathematical perspective, we say that we are strengthening the function’s signature.

Here is the definition of the auxiliary function:
; turn a list of relative distances into a list of absolute distances
;    relative to the already accumulated distance n
; accumulator: n is the sum of numbers between l_0 and l
(define-metafunction Lon
  absolute-accu : l n -> l
  [(absolute-accu () n) ()]
  [(absolute-accu (n_head n_rest ...) n)
   ,(cons (+ (term n) (term n_head))
          (term (absolute-accu (n_rest ...) ,(+ (term n) (term n_head)))))])
In some sense, defining such functions is straightforward. In a different sense, this function is unique. To be precise, it differs from all other recursive functions you have seen so far. The key difference is that both arguments to the recursive call change, not just one. Furthermore, one of the arguments is a part of the original argument (structural recursion), the other one is a number that is not a part of the any structure.

"relative-to-absolute.rkt"

#lang racket
 
(require redex)
 
(define-language Lon
  (l (n ...))
  (n number))
 
(define example1 (term (1.7 3.2 2.1)))
(define example2 (term (1.7 4.9 7.0)))
 
; turn a list of relative distances
(define-metafunction Lon
  absolute : l -> l
  [(absolute l) (absolute-accu l 0)])
 
; turn a list of relative distances into a list of absolute
; distances relative to the already accumulated distance n
; accumulator: n is the sum of numbers between l_0 and l
(define-metafunction Lon
  absolute-accu : l n -> l
  [(absolute-accu () n) ()]
  [(absolute-accu (n_head n_rest ...) n)
   ,(cons (+ (term n) (term n_head))
          (term (absolute-accu (n_rest ...)
                               ,(+ (term n) (term n_head)))))])
 
(test-equal (term (absolute ()))
            (term ()))
(test-equal (term (absolute (1 1 1)))
            (term (1 2 3)))
(test-equal (term (absolute ,example1))
            (term (1.7 ,(+ 1.7 3.2) ,(+ 1.7 3.2 2.1))))

Figure 3: From relative to absolute distances

Figure 3 shows the complete solution to the problem.

7.3 Designing with Accumulators

The absolute-accu function is an example of a function that uses an accumulator. The design of accumulator-based functions is initiallyExperienced programmers recognize the problem before they even write down the template a reaction to a convoluted structural design, that is, when you recognize that your function needs to traverse a structural piece of data several times because it “forgets” the pieces that it has already processed. In the above example, the first design of absolute forgets the numbers that it has seen.

As far as the design of accumulator functions is concerned, it differs from plain structural recursions in four points:
  1. First determine the purpose of the accumulator. Write it down as a purpose statement that explains the accumulator as what it remembers about the difference between the root of the given data structure and the current point.

    In our running example, the complete list is l_0 and the current list l is a part of it. For example, if we start with

      1.7    3.2   2.1

    then after two recursive calls, the current sequence is

      2.1

    meaning that the difference between the two lists are the numbers

      1.7    3.2

    Given the purpose of our function, it suffices to keep the sum of this difference and that is precisely what the accumulator statement says:
    ; accumulator: n is the sum of numbers between l_0 and l
    (define-metafunction Lon
      absolute-accu : l n -> l
      ...)
    In other applications, you may need some other combination of the numbers or you may need all of them including their ordering.

  2. The second step is to decide on what the initial value should be for the accumulator. In the case of a running sum, it is obviously 0.

  3. The third step is to formulate the argument for the recursive call(s) so that the accumulator statement is maintained. In our example, it is relatively obvious that we need to add the first element to the current value of the accumulator, i.e.,

    ,(+ (term n) (term n_head))

  4. Lastly, you need to figure out when to use the accumulator value. It may become the result of the computation when the major structural argument is exhausted; it may contribute to the result in another way; or it may simply be used to terminate the algorithm. The running example adds the accumulator to each element of the resulting list, that is,

    ,(cons (+ (term n) (term n_head)) ...)

For more on accumulator design see HtDP , especially part IV.

In the area of programming languages, accumulator-style functions are commonly used to check context-sensitive properties of programs. The accumulator’s purpose is after all to keep track of the context of the given argument.