Page History

...

;; 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))]))   

...

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

...

;; 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 above examples can thus be written in terms of foldr, by simply supplying the appropriate accumulator generating function and the accumulator base value:

(define (sum_rev lon)
    (foldr + 0 lon))

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

...

(define (f_fwd loa)
    (cond
        [(empty? loa) base]
        [(cons? loa)
            (local
                 [(define (helper acc loa2)
                      (cond
                          [(empty? loa2) acc]
                          [(cons? loa2) (helper (... (first loa2)...acc...) (rest loa2))]))]
                 (helper (...(first loa)...base...) (rest loa)))]))   

It is very tempting to say that the above is equivalent to:

We can clearly see the non-recursive outer function and the recursive helper function.   The accumulator value is calculated and passed forward via an extra input parameter on the helper function.   We can also see that the empty cases of the two functions are not the same.   In particular, the helper's empty case returns the accumulator value while the outer function's empty case performs some base operation.

Here are the two reverse accumulation examples above written in a forward accumulation style:

(define (sum_fwd lon)
  (cond

(define (f_fwd loa)
    (cond
        [(empty? loa) base]
        [(consempty? loalon) 0]
       [(cons? lon)
     (local
                 [(define (helper acc loa2aLon)
                      (cond
            [(empty? aLon) acc]
            [(emptycons? loa2aLon) acc]
                          [(cons? loa2) (helper (...+ (first loa2aLon)...acc... acc) (rest loa2aLon))]))]
       (helper (first lon) (rest lon)))]))

(define (get_largest_pos_fwd lon)
  (cond
    [(helperempty? base loa))]))   

But to make that leap requires 2 conditions to be true:

1. The "..."'s in both the helper and the outer cons? clause must be identical.
2. "base" must represent a value, as opposed to something such as a exception.

For instance, the finding the largest element in a list follows only the first template:

(define (get_largest lon)
lon) 0]
    [(cons? lon)
     (local
       [(define (helper acc aLon)
          (cond
    [        [(empty? lon) (error "no largest in an empty list")]
    [(cons?aLon) acc]
            [(cons? aLon) (helper (if (> (first aLon) acc) (first aLon) acc) (rest aLon))]))]
       (helper (if (> (first lon) 0) (first lon) 0) (rest lon)))]))  

A Forward Accumulation Special Case

It is very tempting to say that the above is equivalent to:

(define (f_fwd loa)
    (cond
        [(empty? loa) base]
        [(cons? loa)
            (local
                 [(define (helper acc loa2)
                      (cond
                          [(empty? loa2) acc]
                          [(cons? loa2) (helper (... (first loa2)...acc...) (rest loa2))]))]
                 (helper base loa))]))   

But to make that leap requires 2 conditions to be true:

1. The "..."'s in both the helper and the outer cons? clause must be identical.
2. "base" must represent a value, as opposed to something such as a exception.

For instance, the finding the largest element in a list follows only the first template:

(define (get_largest lon)
  (cond
    [(empty? lon) (error "no largest in an empty list")]
    [(cons? lon)
     (local
       [(define (helper acc lon2)
          (cond
            [(empty? lon2) acc]
            [(cons? lon2) (helper (if (> (first lon2) acc) (first lon2) acc) (rest lon2))]))]
       (helper (first lon) (rest lon)))]))   

That said, let us consider this special case, where the two above conditions do actually hold.   In that case, we can collapse our template down further, with a requisite name change as well:

;; 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))]))   

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:

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

foldl is a higher order function that performs a foward accumulation algorithmic process on a list when a well-defined base value exists.

We can see by this analysis that a foldl-type forward accumulation requires 2 parts, the two input parameters to foldl other than the list itself:

• A function that takes first and the accumulator and calculates the next accumulator value.
• A base value that is the intial accumulator value.

 Hey!  Aren't those exactly the same two parts that we said that reverse accumulation requires?   What is this saying about forward and reverse accumulation?

Forward and reverse accumulation are just opposite directions for traversing a data structure as it is being processed and thus are fundamentally the same process.

For instance, the examples we have been using above are independent of the direction in which the list is traversed,   We can write them in terms of foldl as well:

(define (sum_fwd lon)
     (local
foldl +      [0 lon))

(define (helper acc lon2)
          (condget_largest_pos_fwd lon)
   (foldl         [(empty? lon2) acc](lambda (x rr)
            [(cons? lon2) (helper (if (> (firstx lon2rr) acc) (first lon2) acc) (rest lon2))]))]
x rr))
           (helper (first lon) (rest lon)))]))   0
          lon))  

But isn't this exactly the same code as above for the reverse accumulation case, where we just substituted foldl for foldr? Does this make sense?