Problem Set 9: Similarities

Submit this assignment to ps9 on Handin.

Note: Whenever you write a function in this class, follow the design recipe. You will be graded accordingly.

1 Removing

; A ListOfNumbers is one of:

; - empty

; - (cons Number ListOfNumbers)

Problem 1. Design a function remove-even that removes every even number from a list of numbers.

Problem 2. Design a function remove-negative that removes every negative number from a list of numbers.

Problem 3. How are remove-even and remove-negative similar? Compare their signatures, purpose statements and definitions. Put your answer in a comment.

2 Tabulating

Problem 4. Provide the missing tests for the following two functions. Use check-within.

; tab-sin : NaturalNumber -> ListOfNumbers

; tabulates sin between n and 0 (inclusive) in a list

(define (tab-sin n)

(cond [(zero? n)     (list (sin 0))]

[(positive? n) (cons (sin n) (tab-sin (sub1 n)))]))

; tab-sqrt : NaturalNumber -> ListOfNumbers

; tabulates sqrt between n and 0 (inclusive) in a list

(define (tab-sqrt n)

(cond [(zero? n)     (list (sqrt 0))]

[(positive? n) (cons (sqrt n) (tab-sqrt (sub1 n)))]))

Problem 5. How are tab-sin and tab-sqrt similar? Compare their signatures, purpose statements and definitions. Put your answer in a comment.

Problem 6. Design a function tab-sqr that tabulates sqr between the input n and 0 (inclusive) in a list.

3 Having

Problem 7. Design a function has-< that checks if some number in a given list of numbers is less than a given number.

Problem 8. Design a function has-string=? that checks if some string in a given list of strings is the same as a given string. (Don’t forget to write the necessary data definition.)

Problem 9. How are has-< and has-string=? similar? Compare their signatures, purpose statements and definitions. Put your answer in a comment.

4 Nonempty lists

Problem 10. How are NEListOfNumbers and NEListOfBooleans similar? Put your answer in a comment.

Problem 11. Because the data definitions for nonempty lists are different from the data definitions for lists, the templates for processing nonempty lists are also different from the templates for processing lists. Finish writing the following templates:

; process-nelon : NEListOfNumbers -> ...

(define (process-nelon nelon) ...)

; process-nelob : NEListOfBooleans -> ...

(define (process-nelob nelob) ...)

Problem 12. Write the data definition and template for NEListOfStrings. Then, 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.) Use the built-in string-length function.

Problem 13. Write the data definition and template for a NEListOfPosns. Then, 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.) Use the dist function below, but provide the missing tests for it:

; dist : Posn Posn -> Number

; computes the distance between two Posns

(define (dist p1 p2)

(sqrt (+ (sqr (- (posn-x p1) (posn-x p2)))

(sqr (- (posn-y p1) (posn-y p2))))))

(check-expect ??? ???)

(check-expect ??? ???)

Problem 14. How are shortest-string and closest-posn similar? Compare their signatures, purposes, and definitions. Put your answer in a comment.

5 Trees

Problem 15. Design a function sum-tree that adds up all the numbers in a TreeOfNumbers.

Problem 16. Design a function prod-tree that multiplies together all the numbers in a TreeOfNumbers.

Problem 17. How are sum-tree and prod-tree similar? Compare their signatures, purpose statements and definitions. Put your answer in a comment.

Problem 18. Write the data definition for a TreeOfStrings. Then, design a function count-tree that counts how many node0s there are in a TreeOfStrings.

Problem 19. How are sum-tree and prod-tree and count-tree all similar? Compare their signatures, purpose statements and definitions. Put your answer in a comment.