In this module we introduce the notions of abstraction and accumulators. First we show how recursive functions can be rewritten to maintain information during each recursive call using accumulators. Second we upgrade to the Intermediate Student Language which allows functions as values. We then show how functions can consume/produce other functions allowing for more abstract, and more elegant, designs.

  1. Given a function that uses mutual recursion, convert it to use accumulators.
  2. Document accumulator arguments by writing an invariant.
  3. Write a function definition that is local in scope to another function.
  4. Given a set of Scheme functions that contain duplicative code, write the abstracted function.
  5. Given a data definition for tree structured data, write a template.
  6. Given a specification for information represented as a tree, write a data definition that maps the information into Scheme data.
  7. Recognize patterns for built-in abstract functions.
  8. Write the contracts for the built-in abstract functions.
  9. Given abstract functions, use Higher Order Function Composition to define a new function.
  10. Given a function that uses structural decomposition, convert it into a function that uses Higher Order Function Composition.
  11. Given a signature that takes other functions as arguments, write down valid inputs for the signature.
  12. Given a recursive data definition, write a fold function.
  13. Recognize patterns for built-in abstract functions.
  14. Write the contracts for the built-in abstract functions.
  15. Given abstract functions, use Higher Order Function Composition to define a new function.
  16. Given a signature that takes other functions as arguments, write down valid inputs for the signature.
  17. Given a function that uses structural decomposition, convert it into a function that uses Higher Order Function Composition.
  18. Given a recursive data definition, write a fold function.
  19. Write an anonymous function using the keyword lambda.
  20. Write a call to an anonymous function with the appropriate number of inputs.
  21. Given a Scheme expression, write down the sequence of steps taken during evaluation.
  22. Use the syntactical conventions for function definitions.
  23. Given a Scheme function, identify the strategy used.
  • DUE DATE: Monday November 20th at 11:59pm

S-Expressions

You are given the following data definition


;; An S-Expression (SExp) is one of 
;; - Atom 
;; - List<SExp>
;; INTERP: represents an s-expression

;; An Atom is one of 
;; - Number
;; - String 
;; - Symbol 
;; - Boolean 
;; INTERP: represents atomic values
  1. Provide the deconstructor template for SExp
  2. Design a function that given an SExp returns the total number of Atoms in the SExp.
  3. Design a function that given an SExp returns a list of all Symbols in the SExp.
  4. Design a function that given an SExp returns the sum of all Numbers in the SExp.
  5. Design a function that given an SExp and two strings s1 and s2 returns a new SExp where all instance of s1 have been replaced with s2.

Higher Order Functions

DrRacket has lots of abstract functions for processing lists (pg. 313, Sect. 21.2, or the online version).

Given the following data definitions: 


(define-struct grade (letter num))
;; A Grade is: (make-grade LetterGrade Number)
;; INTERP: represents a homework grade as 
;;         a letter grade and number grade

;; A LetterGrade is one of:
;; - 'A  >= 90
;; - 'B  >= 80
;; - 'C  >= 70
;; - 'D  >= 60 
;; - 'F  < 60

;; A List<Grades>
(define grades (list (make-grade 'D 62) (make-grade 'C 79) 
                     (make-grade 'A 93) (make-grade 'B 84) 
                     (make-grade 'F 57) (make-grade 'F 38) 
                     (make-grade 'A 90) (make-grade 'A 95)
                     (make-grade 'C 76) (make-grade 'A 90) 
                     (make-grade 'F 55) (make-grade 'C 74)
                     (make-grade 'A 92) (make-grade 'B 86) 
                     (make-grade 'F 43) (make-grade 'C 73)))

Design the requested functions to manipulate Grades. You must use the given list as one of your tests. For each you may use a local expressions.

Note: if you do not use the DrRacket higher order functions from Section 21.2 in the book, you will not receive credit for the sub-problem!

  1. Design the function log->lon that converts a List<Grade> into a List<Number> that contains just the numerical grade, using the Scheme function map.
  2. Using foldr, design the function best-grade that finds the highest Grade in a List<Grade>.
  3. Design a function just-As that returns a list of only the 'A grades, using filter.
  4. Use andmap to design the function all-pass? that checks to see if all the Grades in a given list are not 'F.
  5. Finally design the function bonus that adds 5 to all of the Grades in a given list, and updates the letter portion of the Grade if it changes. Use map to design your function... it must return a List<Grade>!

Trees

A friend of your found this online quiz that they are trying to solve and they are stuck. Help them out by solving these questions.

Provide your solutions without using any abstract functions.

  1. Provide a data definition for a Binary Search Tree that contains non-negative Integers (BSTI) and answer the following questions
    1. Design a function that given a BSTI returns the sum of all the integers found inside the BSTI.
    2. Design a function that given a BSTI returns the product of all the integers found inside the BSTI.
    3. Design a funciton that given a BSTI and a non negative integer dx multiplies each integer in the BSTI by dx.
  2. Provide a data definition for a Binary Search Tree that contains Strings (BSTS). Your BSTS should use alphabetical ordering to decide which string should be stored to the left or right subtree. Answer the following questions for a BSTS
    1. Design a function that given a BSTS appends all the strings in the BSTS using an in-order traversal.
    2. Design a function that given a BSTS and a String ds appends ds to each string in the BSTS.
  3. Provide a data defintion for a tuple. A tuple always contains 2 values, the first value is a string and the second value is a non-negative integer. Provide a data definition of a Binary Search Tree that can contain Tuples (BSTT). Your BSTT should use the alphabetical ordering on the String inside the Tuple's in order to decide which tuple should be stored to the left or right subtree of a node. Answer the following questions on BSTT
    1. Design a function that given a BSTT returns the sum of all Integer values in the Tuples found in the BSTT.
    2. Design a function that given a BSTT appends all the String values in the Tuples found int he BSTT using an in-order traversal.
    3. Design a function that given a BSTT returns a BSTS that holds only the String values found in each Tuple in the BSTT.

Now that you have a solution for the 3 different Binary Search Trees we would like to generalize (or abstract) over the data definition and your solution(s).

  1. Provide a generic data definition for a BST (GBST) that can take any kind of data as an element.
  2. The solutions to 1.c., 2.b., and 3.c. are similar. Use your existing solutions to design a generic function on GBST. Use your generic function to provide a second solution to 1.c., 2.b., 3.c.
  3. The solutions to 1.a., 1.b., 2.a., 3.a. and 3.b are similar. Use your existing solutions to design a generic function on GBST. Use your generic function to provide a second solution to 1.a., 1.b., 2.a., 3.a. and 3.b.