8.12

### Lab 13: AccumulatorsðŸ”—

When you write a function using an accumulator, you must provide an accumulator statement.

Let’s review a simple example. Assume you have a list of numbers and you want to calculate the sum of those numbers. You have learned many ways of doing this already; here it is done using an accumulator.

 ; sum : [ListOf Number] -> Number ; sums the numbers in the given list (define (sum lon) (local [; sum/a : [ListOf Number] Number -> Number ; adds the numbers in the list one by one to the second argument ; *Accumulator*: sum-so-far is the sum of numbers seen so far ; ; examples: ;   lon                 sum-so-far     output ; ------------------------------------------------------ ;   (list 1 2 3 4 5)              0    (+ 0 1 2 3 4 5) ;   (list 2 3 4 5)       0 + 1 =  1    (+ 0 1 2 3 4 5) ;   (list 3 4 5)         1 + 2 =  3    (+ 0 1 2 3 4 5) ;   (list 4 5)           3 + 3 =  6    (+ 0 1 2 3 4 5) ;   (list 5)             6 + 4 = 10    (+ 0 1 2 3 4 5) ;   empty               10 + 5 = 15    (+ 0 1 2 3 4 5) ; (define (sum/a lon sum-so-far) (cond [(empty? lon) sum-so-far] [else (sum/a (rest lon) (+ (first lon) sum-so-far))]))] (sum/a lon 0))) (check-expect (sum (list 1 2 3 4 5)) (+ 0 1 2 3 4 5))

Note that every such function will have a helper written using an accumulator. Both the original function sum and the helper sum/a need their signatures and purpose statements clearly indicated. For every function using an accumulator, we need to clearly identify the accumulator and write an accumulator statement. An accumulator statement should explain what the accumulator is, not how to use or change the accumulator.

As usual, we also need to write examples for every function. A function using an accumulator should have many examples, because each time the original function is used once, the helper is used many times. In the function sum above, all the examples for sum/a arise from the one and only example for sum. Each example for sum/a shows the list being processed and the accumulator being updated.

Exercise 1. The sum/a function above is defined locally. Convert it to a top-level definition and convert all the examples to tests. Write a new test for sum and write all the corresponding tests for sum/a.

For each remaining exercise in this lab, we describe a strategy for using an accumulator. Your job is to design a helper function that uses an accumulator in the way we describe. You also need to design an original function that calls the helper function and passes the initial accumulator value.

Exercise 2. Design a function alternating-sum to compute the alternating sum of all elements in a list of numbers.
 (check-expect (alternating-sum empty) 0) (check-expect (alternating-sum (list 1 4 9 16 9 7 4 9 11)) (+ 1 -4 9 -16 9 -7 4 -9 11))
Your helper function should use accumulators in the following way: (We have provided the accumulator statements.)
 ; An Operation is one of: ; - "add" ; - "subtract" ; *Accumulator*: operation is whether to add or subtract the next number ; *Accumulator*: sum-so-far is the sum of numbers seen so far ; examples: ;   numbers                       operation     sum-so-far       output ; ----------------------------------------------------------------------- ;   (list 1 4 9 16 9 7 4 9 11)    "add"           0              -2 ;   (list   4 9 16 9 7 4 9 11)    "subtract"      0 +  1 =   1   -2 ;   (list     9 16 9 7 4 9 11)    "add"           1 -  4 =  -3   -2 ;   (list       16 9 7 4 9 11)    "subtract"     -3 +  9 =   6   -2 ;   (list          9 7 4 9 11)    "add"           6 - 16 = -10   -2 ;   (list            7 4 9 11)    "subtract"    -10 +  9 =  -1   -2 ;   (list              4 9 11)    "add"          -1 -  7 =  -8   -2 ;   (list                9 11)    "subtract"     -8 +  4 =  -4   -2 ;   (list                  11)    "add"          -4 -  9 = -13   -2 ;   empty                         "subtract"    -13 + 11 =  -2   -2
So, do not use generative recursion; stick with structural recursion and follow the template for processing a list of numbers.

Exercise 3. Design a function funky that takes a [ListOf 1String] as input and produces the same [ListOf 1String] as output, except the output should alternate between upper-case and lower-case.
 (check-expect (funky empty) empty) (check-expect (funky (explode "Computer Science")) (explode "CoMpUtEr sCiEnCe"))
Your helper function should use an accumulator in the following way: (You must provide an accumulator statement.)
 ; A Case is one of: ; - "up" ; - "down" ; examples: ;   letters                         case      output ; -------------------------------------------------------------------------- ;   (explode "Computer Science")    "up"      (explode "CoMpUtEr sCiEnCe") ;   (explode  "omputer Science")    "down"    (explode  "oMpUtEr sCiEnCe") ;   (explode   "mputer Science")    "up"      (explode   "MpUtEr sCiEnCe") ;   (explode    "puter Science")    "down"    (explode    "pUtEr sCiEnCe") ;   (explode     "uter Science")    "up"      (explode     "UtEr sCiEnCe") ;   (explode      "ter Science")    "down"    (explode      "tEr sCiEnCe") ;   (explode       "er Science")    "up"      (explode       "Er sCiEnCe") ;   (explode        "r Science")    "down"    (explode        "r sCiEnCe") ;   (explode         " Science")    "up"      (explode         " sCiEnCe") ;   (explode          "Science")    "down"    (explode          "sCiEnCe") ;   (explode           "cience")    "up"      (explode           "CiEnCe") ;   (explode            "ience")    "down"    (explode            "iEnCe") ;   (explode             "ence")    "up"      (explode             "EnCe") ;   (explode              "nce")    "down"    (explode              "nCe") ;   (explode               "ce")    "up"      (explode               "Ce") ;   (explode                "e")    "down"    (explode                "e") ;   (explode                 "")    "up"      (explode                 "")
So, do not use generative recursion; stick with structural recursion and follow the template for processing a [ListOf 1String]. Use string-upcase and string-downcase.

Exercise 4. Design a function sentence that takes a [ListOf 1String] as input and produces the same [ListOf 1String] as output, except the first 1String should become upper-case, and whenever a period appears, the next non-whitespace 1String should also become upper-case. This process is like how automatic capitalization works on some keyboards.
 (check-expect (sentence empty) empty) (check-expect (sentence (explode "hey. whats up")) (explode "Hey. Whats up"))
Your helper function should use an accumulator in the following way: (You must provide an accumulator statement.)
 ; examples: ;   letters                      capitalize    output ; ------------------------------------------------------------------------ ;   (explode "hey. whats up")    true          (explode "Hey. Whats up") ;   (explode  "ey. whats up")    false         (explode  "ey. Whats up") ;   (explode   "y. whats up")    false         (explode   "y. Whats up") ;   (explode    ". whats up")    false         (explode    ". Whats up") ;   (explode     " whats up")    true          (explode     " Whats up") ;   (explode      "whats up")    true          (explode      "Whats up") ;   (explode       "hats up")    false         (explode       "hats up") ;   (explode        "ats up")    false         (explode        "ats up") ;   (explode         "ts up")    false         (explode         "ts up") ;   (explode          "s up")    false         (explode          "s up") ;   (explode           " up")    false         (explode           " up") ;   (explode            "up")    false         (explode            "up") ;   (explode             "p")    false         (explode             "p") ;   (explode              "")    false         (explode              "")
So, do not use generative recursion; stick with structural recursion and follow the template for processing a [ListOf 1String]. Use string-upcase and string-whitespace?.

Exercise 5. Interpret a list of numbers as a sequence of deposit and withdrawal transactions in the same bank account, ordered from oldest to newest. Design a function overdrawn? that takes such a list as input, starting with opening the account, and returns a boolean that says whether the account balance ever becomes negative at any point in the history of the account.
 (check-expect (overdrawn? (list 20 100 -80)) false) (check-expect (overdrawn? (list 20 -80 100)) true) (check-expect (overdrawn? (list 100 -80 20)) false)
Use an accumulator that is the current account balance.