Page History

...

Let's look at how we would sum a list of numbers using "forward 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.

...

;; foldl: (lambda any1 any2 --> any2) any2 list-of-any1 --> any2
(define (foldl func base loa)
   (cond
      [(empty? loa) base]
      [(cons? loa)
       (local
          [(define (helper acc loa2)
              (cond
                 [(empty? loa2) acc]
                 [(cons? loa2) (helper (func (first loa2) acc ) (rest loa2))]))]
          (helper base loa))]))   

It is important to emphasize again that this is a special case where a base value is well-defined.   The general case template above will always work and should be the template of choice if you are not sure how to write your forward accumulation algorithm.   Once you get it working, you can convert it to the more specialized case here if it warrants it.  

Once again, our template has reduced down to the 100% concrete code of a higher-order function. Here, the function is called "foldl" ("fold-left") and is the same as the foldl defined in the last lab:

...