Assignment 9
Due Date Thursday 02/14 at 9pm
Purpose To practice recursive data processing.
You should submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept NO email submissions. Failure to submit a .rkt file will result in a 0.
You are only allowed to use the language specified at the top of this page: failure to do so will result in a 0.
Your code MUST conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses so please remember to read it before submitting each assignment.
You must follow all the steps of the design recipe when completing this assignment.
Please be sure to look at the feedback for assignment 7 before submitting, as we will be grading you more harshly on things we have warned you about before.
You must submit this assignment with your partner. Please make sure you can submit with your partner before 5pm on Thursday or we cannot guarantee that you will be able to submit your homework before the deadline. If the course staff are unable to assist you after 5pm and this causes your homework to be late we will not grant an extension.
You should not use list for this assignment (but you may use cons).
Exercise 1 Complete the steps of the data design recipe for the following data definition:
(define-struct plist [frst rst]) ; A PseudoLON is one of: ; - "empty" ; - (make-plist Number PseudoLON)
Exercise 2 Complete the steps of the function design recipe for the following function:
(define (add-up-all plon) (cond [(string? plon) 0] [(plist? plon) (+ (plist-frst plon) (add-up-all (plist-rst plon)))]))
Exercise 3 Consider the following example of a PseudoLON:
(define PLIST1 (make-plist 17 (make-plist 18 19)))
How will the program break if we call (add-up-all PLIST1)? Why? Write your answers in a comment. NOTE: This is two questions so we expect two answers.
Exercise 4 Complete the steps of the data design recipe for the following data definition:
; A LON is one of: ; - '() ; - (cons Number LON)
Exercise 5 Complete the steps of the function design recipe for the following function:
(define (add-lon lon) (cond [(empty? lon) 0] [(cons? lon) (+ (first lon) (add-lon (rest lon)))]))
Exercise 6 Consider the following example of a LON:
How will the program break if we call (add-lon LIST1)? Why? Write your answers in a comment. NOTE: This is two questions so we expect two answers.
Exercise 7 Design the function all-in-order? which takes a list of Strings and returns #true if all the Strings are in alphabetical order and #false otherwise. Remember to follow the data design recipe for any data definitions you need to provide. REMEMBER: You should be following the template for your input data. You should not access data that is deeply nested (e.g. the first element of the rest of a list).
Exercise 8 Design the function smoosh which takes a list of Images and places the images next to each other in order (so Images that appear closer to the front of the list should appear further to the left in the result). You may not use apply. For an empty list the empty-image will come in handy. Remember to follow the data design recipe for any data definitions you need to provide. NOTE: Please do not copy and paste images into your check-expects. You may, however, define some constant images and utilize them in your tests.
Exercise 9 Design the function root-the-squares which takes a list of Numbers and returns a list of the square roots of all the perfect squares.
Exercise 10 Two sets are equal if they both contain all the same elements. Suppose we represent a set as a list of Numbers. Then the set (cons 1 (cons 2 (cons 3 '()))) and the set (cons 1 (cons 1 (cons 1 (cons 1 (cons 2 (cons 2 (cons 2 (cons 3 (cons 3 '()))))))))) are the same. Design the function set=? which, given two lists of Numbers, determines if they are the same set.
HINT: Two sets are equal if they both contain all the elements of the other.