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 number 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 3 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

Exercise 22. Design a function select-tree-result that takes a SelectTree and produces the sorted list of numbers. Hint: Instead of generative recursion, stick with structural recursion and follow the template for processing a SelectTree.

The goal of the rest of this section is to generate a SelectTree from a list of numbers. The problem decomposition can use some helper functions.

Exercise 23. Design a function smallest-number that takes a non-empty list of numbers and finds the smallest number in it. (You did this in Problem set 8: Abstraction. You can do it here with or without any helper function.)

Exercise 24. Design a function remove-number that takes a non-empty list of numbers and a number in it, and removes the given number to produce a shorter list. If the given number occurs multiple times in the given list, then remove the first occurrence only.

Exercise 25. Design a function generate-select-tree that decomposes a given list of numbers into a SelectTree. Follow the decomposition strategy in Exercise 20.

Hint: Use generative recursion. Use smallest-number and remove-number. When you write a generative recursive function, you must provide a termination argument. A termination argument must say why the function always eventually stops, not just when it stops.

Exercise 26. Design a function that sorts a list of numbers using generate-select-tree and select-tree-result.

Exercise 27. (optional) The data definition above for a SelectTree uses the defined structures done and select. Change the data definition to use the built-in structures empty and cons instead, and revise all the functions in this section to match. Why would select-tree-result be no longer needed?