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.
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.
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.
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.
Use an accumulator that is the current account balance.