On this page:
1 Abstraction Practice:   Lists
2 Abstraction Practice:   Trees
6.10.1

Assignment 8: Abstraction

This assignment is due on Wednesday, 10/18 at 11:59 PM. Submit it using the Handin server as assignment a8.

Note: Use the "Intermediate Student with lambda" language on this and further assignments in this course.

Note: Whenever you abstract from concrete things, remember to re-define them using the new abstraction. (You don’t need to submit the original versions.) They should have the same signatures and purpose statements as before as well as pass the same tests as before. (Helpers are often useful for eliminating inessential differences among concrete things.) The new abstraction should have its own signature and purpose statement. If the original tests do not provide sufficient coverage for the abstraction, include additional tests.

1 Abstraction Practice: Lists

Don’t use the built-in list abstractions unless otherwise indicated.

Exercise 1 Abstract from the functions lighten and enlarge in Assignment 7 (Exercises 10 and 11).

Exercise 2 Do Exercise 241 in How to Design Programs, Second Edition. Note that this exercise depends on data definitions discussed below Exercise 143 and in Exercise 147. Develop these data definitions first.

Then, write two examples each of NEListOfString, NEListOfPosn, and NEListOfImage.

Exercise 3 Abstract from the following functions:
  • Design a function shortest-string that takes a nonempty list of strings as input and returns the shortest string. (If multiple strings are equally short, return any of them.)

  • Design a function closest-posn that takes a nonempty list of Posns as input and returns the Posn closest to the origin. (If multiple Posns are equally close to the origin, return any of them.)

  • Design a function shortest-list that takes a nonempty list of lists of images as input and returns the shortest list. (If multiple lists are equally short, return any of them.)

Exercise 4 Abstract from the following functions:
  • Design a function remove-even that removes every even number from a list of numbers.

  • Design a function remove-empty that removes every empty list from a list of lists of numbers.

Exercise 5 Do Exercise 250 in How to Design Programs, Second Edition. Of course, the resulting tabulation functions for sqr and tan should be called tab-sqr and tab-tan respectively.

Exercise 6 Abstract from the following functions:
  • Design a function has-< that checks if some number in a list of numbers is less than a given number.

  • Design a function has-string=? that checks if some string in a list of strings is same as a given string.

  • Design a function has-empty? that checks if some list in a list of lists of images is empty.

  • (Optional) The "helper to process a ListOfZombies" in Exercise 15 of Assignment 6.

You may use ormap on this exercise.

Exercise 7 (Advanced) Do this exercise using map and without recursion. Design a function that takes a list of numbers and multiplies every number in the list by a given number. Then design a function mul-table that makes a multiplication table (a list of lists of numbers) using a given list of numbers. Hint: Use local.

Here are two examples of the desired behavior:
(check-expect (mul-table empty) empty)
(check-expect (mul-table (list 2 3 5 10))
              (list
               (list 4 6 10 20)
               (list 6 9 15 30)
               (list 10 15 25 50)
               (list 20 30 50 100)))

2 Abstraction Practice: Trees

Here is the data definition for a binary tree of numbers. A leaf only contains a number, whereas a node contains a number and one or two child trees.

;; A TreeOfNumber is one of:
;;  - (make-leaf Number)
;;  - (make-node1 Number TreeOfNumber)
;;  - (make-node2 Number TreeOfNumber TreeOfNumber)

Exercise 8 Design a function sum-tree that adds up all the numbers in a TreeOfNumber. Design another function prod-tree that multiplies together all the numbers.

Exercise 9 Abstract sum-tree and prod-tree into a single function op-tree. As usual when you abstract, use op-tree to re-define sum-tree and prod-tree.

Exercise 10 Design the function count-tree that counts how many leaves there are in a TreeOfNumber.

Exercise 11 Abstract sum-tree, prod-tree, and count-tree into a single function process-tree. Is this the same as the op-tree function you defined earlier? (Put your answer in a comment.) Again as usual, re-define the previous functions using your new function.

Exercise 12 Generalize TreeOfNumber to [Tree X], which should support trees of any kind of data. Hint: first write another data definition similar to TreeOfNumber for a different kind of data, then abstract from the two data definitions you have. Again as usual, use your new data definition to re-define TreeOfNumber.

Exercise 13 Generalize process-tree to work over [Tree X]. Do you need to change the body of the function? (Put your answer in a comment.)

Exercise 14 Generalize count-tree to work over [Tree X]. Do you need to change the body of the function? (Put your answer in a comment.)