Assignment 8: Abstraction
Due Date: Thursday March 9 2017, 12:00 PM
Important Note Whenever we say to “design a function”, we mean that you need to follow the design recipe. Any other time that you write a function in this class, you also need to follow the design recipe.
Important Note Use Intermediate Student on this assignment, and further assignments in this course.
1 Map and Fold
Exercise 1 Design a function smallest which accepts a posn and list of posn uses either foldl or foldr to find the posn clossest to the given posn. You should use local to define a local helper function.
Excercise 2 Write a function count which accepts a list of numbers, and which uses either the built-in racket foldl or foldr functions, and counts the number of items in the list. You may NOT use the built in length function in this excercise. You will have to write an auxilary function which is given to the foldl or foldr functions which will perfom the counting.
Test the function with a few list of numbers.
Now abstract this function to work with a list of any data type.
2 Book exercises
Exercises 238, 239, 241, 245
http://www.ccs.neu.edu/home/matthias/HtDP2e/part_three.html
3 Abstracting trees
Here is the data definition for a binary tree of numbers. A leaf only contains a number, and a node contains a number, and one or two child elements.
;; A Tree is one of:
;; – (make-leaf Number)
;; – (make-node1 Number Tree)
;; – (make-node2 Number Tree Tree)
Exercise 3 Design a function sum-tree that adds up all the elements of a Tree. Design another function prod-tree the multiplies together all of the elements.
Exercise 4 Abstract sum-tree and prod-tree into a single function op-tree. Use op-tree to re-define sum-tree and prod-tree.
Exercise 5 Design the function count-tree that counts how many leaves there are in the tree.
Exercise 6 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? Again, redefine the previous functions using your new function.
Exercise 7 Generalize Tree to [Tree X] which should support trees of any kind of data. Use your new definition to redefine Tree.
Exercise 8 Generalize process-tree to work over [Tree X]. Do you need to change the body of the function?