On this page:
2 Abstraction
3 Mutual recursion
4 Generative recursion
8.12

Lab 15: Final exam prep🔗

Remember to follow (and when necessary, adapt) the design recipe for each function.

1 Accumulators🔗

Here is the data definition for a ByTwoN:
; A ByTwoN is one of:
; - empty
; - (make-two Number ByTwoN Number)
(define-struct two [left rest right])

Exercise 1. Design a function count-bytwon that counts how many numbers are in a ByTwoN. Don’t use any helper functions.

Exercise 2. Design a function sum-bytwon that computes the sum of all the numbers in a ByTwoN. Don’t use any helper functions.

Exercise 3. Design a function product-bytwon that computes the product of all the numbers in a ByTwoN. Don’t use any helper functions.

Exercise 4. Re-design all of the functions from Exercises 1, 2, and 3 to use an accumulator. (Keep the old versions for use in the next section.) When you write a function using an accumulator, you must provide an accumulator statement. An accumulator statement should explain what the accumulator is, not how to use or change the accumulator.

2 Abstraction🔗

Exercise 5. Abstract from your functions sum-bytwon and product-bytwon from Exercises 2 and 3 (not 4). You should identify two essential differences, a number and a function. Call your new abstraction fold-bytwon. Remember to write its signature and purpose, and use it to redefine the two original functions.

Exercise 6. Use your abstraction fold-bytwon from Exercise 5 to redefine count-bytwon from Exercise 1 (not 4). You will need to design the function input required by fold-bytwon. Put it in a local, then move it to a lambda.

Exercise 7. Write a data definition ByTwoS that’s like ByTwoN, but has strings rather than numbers as elements.

Exercise 8. Design a function that consumes a ByTwoN and a function from numbers to strings, and applies the function to every number in the given ByTwoN, producing a ByTwoS. You should write at least two tests for this function; feel free to use lambda in these tests.

Exercise 9. Design a function that consumes a ByTwoS and a function from strings to numbers, and applies the function to every string in the given ByTwoS, producing a ByTwoN. You should write at least two tests for this function; feel free to use lambda in these tests.

Exercise 10. Abstract from the two data definitions ByTwoN and ByTwoS. (If you’re not sure how to abstract from data definitions, review Lecture 17: Local definitions Exercise 2 and the video before it. Remember to redefine ByTwoN and ByTwoS using your new abstraction.) Then abstract from your functions in Exercises 8 and 9. (Remember to write the signature and purpose statement of your new abstraction, and use it to redefine the two original functions.)

3 Mutual recursion🔗

Here is the data definition for a StringTree:

; A StringTree is one of:
; - (make-leaf String)
; - (make-node String [ListOf StringTree])
(define-struct leaf (label))
(define-struct node (label kids))

Exercise 11. Write down the data definition for a [ListOf StringTree]. Give two examples of [ListOf StringTree] that are not empty.

Exercise 12. Design a function that takes a StringTree and returns a String consisting of all the labels of the leaves (ignoring the nodes) concatenated together.

Exercise 13. (optional) Design a function that takes a StringTree and returns the length of the longest label on any of the nodes or leaves.

Exercise 14. (optional) Design a function that takes a StringTree and a String and determines if the given String is used as a label on any of the nodes or leaves.

Exercise 15. (optional) Abstract from the 3 functions you designed in the last 3 exercises.

Exercise 16. Design a function that takes a StringTree and returns a StringTree that shortens each label to just its first letter. You may find the function substring or string-ith useful.

Exercise 17. (optional) Design a function that takes a String and a StringTree and returns a StringTree where each label has been modified to include the given String at the beginning. Use the following check-expect to test your function.
(check-expect (prefix-relabel
               "My "
               (make-node "root"
                          (list
                           (make-leaf "leaf1")
                           (make-node "node1"
                                      (list
                                       (make-leaf "leaf2")
                                       (make-leaf "leaf3"))))))
              (make-node "My root"
                         (list
                          (make-leaf "My leaf1")
                          (make-node "My node1"
                                     (list
                                      (make-leaf "My leaf2")
                                      (make-leaf "My leaf3"))))))

Exercise 18. (optional) Abstract from the 2 functions you designed in the last 2 exercises.

4 Generative recursion🔗

Sorting is just one task that can be sped up using generative recursion. In this section, you’ll use generative recursion to speed up a different task: raising a given number to a given power. First you’ll use structural recursion to design a slow solution to the problem; then you’ll use generative recursion to design a fast solution to the problem.

Exercise 19. Design a function power that takes a number x and a natural number n and returns the number that is x raised to the n-th power. Here n is the exponent. Do not use any built-in function for exponentiation.
(check-expect (power 10 3) 1000)
(check-expect (power 2 10) 1024)
(check-expect (power 1.1 4) 1.4641)
Hint: Do not use generative recursion; this exercise is just to warm up. Instead, stick with structural recursion and follow the template for processing a NaturalNumber:
; A NaturalNumber is one of:
; - 0
; - (+ 1 NaturalNumber)

Exercise 20. A typical bank account yields 0.01% interest per day. In such an account, how much money does $1 become in 10,000 days? Compute the answer by running (power 1.0001 10000). How long does the computation take? (You can measure how long it takes using time.)

Exercise 21. Because you designed power by following the template for processing a NaturalNumber, it decomposes the problem (power 1.0001 10000) into the problem (power 1.0001 9999). We can make power faster by decomposing the exponent 10000 differently, into the exponent 5000 instead of 9999. After all, the answer to (power 1.0001 10000) is simply the square of the answer to (power 1.0001 5000).

In general, let’s decompose a NaturalNumber into a PowerTree defined below:
; A PowerTree is one of:
; - (make-zeroth)
; - (make-oddth  PowerTree)
; - (make-eventh PowerTree)
(define-struct zeroth [])
(define-struct oddth  [sub1])
(define-struct eventh [half])
The interpretation of a PowerTree is specified by the following function.
; power-tree-exponent : PowerTree -> NaturalNumber
; returns the meaning of the given PowerTree
(define (power-tree-exponent pt)
  (cond [(zeroth? pt) 0]
        [(oddth?  pt) (+ 1 (power-tree-exponent (oddth-sub1  pt)))]
        [(eventh? pt) (* 2 (power-tree-exponent (eventh-half pt)))]))

Design a function generate-power-tree that takes a natural number and decomposes it into a PowerTree whose interpretation is it. For example, (generate-power-tree 10000) should generate a PowerTree whose interpretation is 10000.
(check-expect (power-tree-exponent (generate-power-tree 10000)) 10000)
To keep the generated PowerTree as small as possible, do not follow the structural recursion template for processing a NaturalNumber. Instead, check if the input is zero, odd, or even.
  • If the input is zero, then just return (make-zeroth) because its interpretation is zero.

  • If the input is odd, then make a recursive call on a natural number that is one less.

  • If the input is even, then make a recursive call on a natural number that is half.

Because this function makes recursive calls without following any processing template, you must remember to make it terminate, and write a termination argument that explains why the function eventually stops; it is not enough to say only when the function stops. Your definition of generate-power-tree should pass these tests:
(check-expect (generate-power-tree 0)
              (make-zeroth))
(check-expect (generate-power-tree 1)
              (make-oddth (make-zeroth)))
(check-expect (generate-power-tree 2)
              (make-eventh (make-oddth (make-zeroth))))
(check-expect (generate-power-tree 4)
              (make-eventh (make-eventh (make-oddth (make-zeroth)))))
(check-expect (generate-power-tree 8)
              (make-eventh (make-eventh
               (make-eventh (make-oddth (make-zeroth))))))
(check-expect (generate-power-tree 9)
              (make-oddth (make-eventh (make-eventh
               (make-eventh (make-oddth (make-zeroth)))))))

Exercise 22. Design a function power-tree-result that takes a number x and a PowerTree pt and returns the number that is x raised to the (power-tree-exponent pt)-th power. But do not use the slow power function you designed, and do not use any built-in function for exponentiation either. Instead, follow the template for processing a PowerTree.
(check-expect (power-tree-result 10
                (make-oddth (make-eventh (make-eventh
                 (make-eventh (make-oddth (make-zeroth)))))))
              1000000000)
In order to fill in the template and complete the definition, you need to turn the recursion outcomes provided by the template into the expected output, so make sure you write enough examples, and perhaps use the table method. For example, to handle the input pt = (generate-power-tree 9), you need to turn the recursion outcome x8 into the expected output x9, by multiplying by x. And to handle the input pt = (generate-power-tree 8), you need to turn the recursion outcome x4 into the expected output x8, by squaring. In general, you need to use the equation x2n = (xn)2.

Because this function follows a processing template, you can be sure that it always terminates, and you do not need to write any termination argument.

Exercise 23. Combine generate-power-tree and power-tree-result to design a function fast-power like power: it takes a number x and a natural number n and returns the number that is x raised to the n-th power. The definition of fast-power is very short, does not use recursion, and can be written just by looking at the signatures of generate-power-tree and power-tree-result. Your fast-power should pass the same tests as power above. Again, do not use the slow power function you designed, and do not use any built-in function for exponentiation either.

Exercise 24. Compute the same answer as Exercise 6 by running (fast-power 1.0001 10000). How long does the computation take? (You can measure how long it takes using time.)