Page History

...

We will call this style of accumulation a Reverse Accumulation algorithm because the result is being accumulated as one "reverses" back out of the data structure.

Here's another example that uses a more generalized notion of "accumulation":

;; 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.

We can extract a template for reverse accumulation algorithms, which is based on the template for a list-of-any:

(define (f_rev loa)
   (cond
       [(empty? loa) base]
       [(cons? loa) (... (first loa)...(f_rev (rest loa))])) 

But we can take this a step further by noting that the "..."'s in the cons? clause just represent some function applied to first and the recursive result. In addition, the "base" is just some parameter that we could have passed in as an input parameter. Thus, we can rewrite the template as follows, including a name change, which I will justify afterwards:

;; foldr: (lambda any1 any2 -> any2) any2 list-of-any1 --> any2
(define (foldr func base loa)
   (cond
       [(empty? loa) base]
       [(cons? loa) (func (first loa)(foldr func base_value (rest loa))])) 

 The template is gone!   The code is now 100% concrete, with nothing left to fill in!   We have defined a function, called "foldr" ("fold-right"), which the same foldr defined in the last lab:

(foldr f base (list x1 x2 ... xn)) = (f x1 (f x2 ... (f xn base)))

Convince yourself that this definition is the generic process of reverse accumulation in a list.

foldr is a higher order function that performs a reverse accumulation algorithmic process on a list.

We can see by this analysis that a reverse accumulation requires 2 parts, the two input parameters to foldr other than the list itself:

• A function that takes first and the accumulator (the recursive result) and calculates the next accumulator value.
• A base value that is the intial accumulator value (that the empty list returns).

The above examples can thus be written in terms of foldr:

(define (sum lon)
    (foldr + 0 lon))

(define (get_largest_pos lon)
   (foldr (lambda (x rr)
              (if (> x rr) x rr))
          0
          lon))  

 "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".   

...

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.

All the "outer" function, "sum_fwd", does is to set up the initial value of the accumulator.  It is is not a recursive function.   Only the helper is recursive.