Page History

...

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

(define (get_largest_pos_fwd lon)
  (cond
    [(empty? lon) 0]
    [(cons? lon)
     (local
       [(define (helper acc aLon)
          (cond
            [(empty? 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:

...

Can you explain the difference?

Tail Recursion

If you look at the templates for forward accumulation, you will see an interesting fact:  every return value is the direct, un-processed return value of a function call, specifically the call to the helper function.   Comparing to the reverse accumulation template, we see that this fact is not true in that scenario.   To directly return the result of a recursive call has a special name, "tail recursion" because the "tail" of the recursive call is returned.   For reasons beyond the scope of our current discussion, it turns out that it is possible to perform additional optimizations on tail-recursive algorithms, namely, one can convert them to loops, which execute much faster and with much less memory than recursive calls.   In fact, in theoretical computer science, loops are nothing more than the special case of optimized tail-recursive algorithms.

Scheme compilers are defined by the Scheme standards to perform tail-recursion optimizations.   We can see this if we run the following code:

;; make-ints: int -> list-of-ints
;; makes a list of ascending integers from n to 1 or empty if n = 0.
;; Examples:
(check-expect (make-ints 0) empty)
(check-expect (make-ints 1) (list 1))
(check-expect (make-ints 2) (list 1 2))
(check-expect (make-ints 3) (list 1 2 3))

(define (make-ints n)
  (cond
    [(zero? n) empty]
    [(positive? n) 
     (local
       [(define (helper acc i)
          (cond
            [(zero? i) acc]
            [(positive? i) (helper (cons i acc) (sub1 i))]))]
       (helper (list n) (sub1 n)))]))


(define ints (make-ints 1000000))

;;max: num num --> num 
;; returns the larger of the two numbers.
;; The following functions both return the largest value in the given list
(time (foldr max 0 ints))
(time (foldl max 0 ints))   

You should see that the foldl version runs significantly faster than the foldr version. And if you comment out foldr and foldl one at a time, try increasing the size of "ints" by a factor of 10, you will see that foldl runs with much less memory than foldr. Why do you think that I wrote "make-ints" as a forward accumulation algorithm?