Lab 15: Final exam prep🔗

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

1 Accumulators🔗

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 16: 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 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 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).

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.)