Lab 9: Built-in abstractions
Note: Whenever you design or write a function, you need to follow the design recipe.
Note: Use the “Intermediate Student with lambda” language on this and further assignments in this course.
Note: This lab is long, but don’t worry. You’ll still get credit even if you don’t finish the whole thing.
1 What is X?
Exercise 1. Design a function called add-six-to-all that takes a list of numbers and produces a new list of numbers by adding 6 to each number.
; map : {X Y} [X -> Y] [ListOf X] -> [ListOf Y] ; constructs a list by applying f to each item on lx ; (map f (list x-1 ... x-n)) == (list (f x-1) ... (f x-n)) (define (map f lx) ...)
- Answer in a comment:
; In the signature of map, X=??? and Y=??? - Copy the signature of map above, then replace X and Y throughout by what you guessed. For instance, if you wrote X=String and Y=Image, then you should end up with
; map : [String -> Image] [ListOf String] -> [ListOf Image] So what’s the signature of the function input to map? Follow the design recipe steps for this function, separately from the design recipe steps for the add-six-to-all function.
Exercise 2. Design a function called odd-strings-only that takes a list of strings and produces a new list of only those given strings whose lengths are odd.
; filter : {X} [X -> Boolean] [ListOf X] -> [ListOf X] ; produces a list from those items on lx for which p holds (define (filter p lx) ...)
- Answer in a comment:
; In the signature of filter, X=??? - Copy the signature of filter above, then replace X throughout by what you guessed. For instance, if you wrote X=String, then you should end up with
; filter : [String -> Boolean] [ListOf String] -> [ListOf String] So what’s the signature of the function input to filter? Follow the design recipe steps for this function, separately from the design recipe steps for the odd-strings-only function.
; dist : Posn Posn -> Number ; compute the distance between the given Posns (check-expect (dist (make-posn 50 100) (make-posn 350 500)) 500) (check-expect (dist (make-posn 50 80) (make-posn 60 80)) 10) (define (dist p q) (sqrt (+ (sqr (- (posn-x p) (posn-x q))) (sqr (- (posn-y p) (posn-y q))))))
- Answer in a comment:
; In the signature of filter, X=??? - Copy the signature of filter above, then replace X throughout by what you guessed. For instance, if you wrote X=String, then you should end up with
; filter : [String -> Boolean] [ListOf String] -> [ListOf String] So what’s the signature of the function input to filter? Follow the design recipe steps for this function, separately from the design recipe steps for the near-origin function.
2 Using local
Exercise 4. Design a function that takes a list of numbers and a number, and returns the list of numbers in the given list that are strictly greater than the given number.
- Answer in a comment:
; In the signature of filter, X=??? Copy the signature of filter, then replace X throughout by what you guessed.
So what’s the signature of the function input to filter? Follow the design recipe steps for this function, separately from the design recipe steps for the main function.
Exercise 5. Design a function that takes a list of strings and a number, and returns the list of strings in the given list that are either equal to "fork" or of length greater than the given number.
- Answer in a comment:
; In the signature of filter, X=??? Copy the signature of filter, then replace X throughout by what you guessed.
So what’s the signature of the function input to filter? Follow the design recipe steps for this function, separately from the design recipe steps for the main function.
Exercise 6. Design a function that takes a Posn and a list of Posns, and returns the list of distances between the given Posn and each Posn in the given list.
- Answer in a comment:
; In the signature of map, X=??? and Y=??? Copy the signature of map, then replace X and Y throughout by what you guessed.
So what’s the signature of the function input to map? Follow the design recipe steps for this function, separately from the design recipe steps for the main function.
3 Combining built-in abstractions
- Answer in comments:
; In the signature of map, X=??? and Y=??? ; In the signature of filter, X=??? Copy the signatures of map and filter, then replace X and Y and X throughout by what you guessed.
Look at what you just replaced, and remember that your main goal is to turn a list of strings into a list of numbers. Which of these two signatures shows an input list of strings? Which of these two signatures shows an output list of numbers?
Exercise 8. Design a function lengths-without-e that takes a list of strings and returns a list of numbers, which are the lengths of those strings that do not contain the letter "e".
- Answer in comments:
; In the signature of map, X=??? and Y=??? ; In the signature of filter, X=??? Copy the signatures of map and filter, then replace X and Y and X throughout by what you guessed.
Look at what you just replaced, and remember that your main goal is to turn a list of strings into a list of numbers. Which of these two signatures shows an input list of strings? Which of these two signatures shows an output list of numbers?
squaring it,
adding 5 to it, and
keeping the result if it ends in either 5 or 6 in decimal.
; square-add-five-omit : [ListOf Number] -> [ListOf Number] ; Squares, adds five, then keeps numbers whose resulting value ; after those two operations ends in either a 5 or 6. (check-expect (square-add-five-omit empty) empty) (check-expect (square-add-five-omit (list 3 9 15 21 10 28)) (list 86 446 105 )) (define (square-add-five-omit lon) (filter DESIGN-THIS-HELPER-FUNCTION (map DESIGN-THIS-HELPER-FUNCTION (map sqr lon))))
4 Calculator
Using the skills you just practiced, you will now develop a program that performs arithmetic operations without triggering any mathematical errors such as dividing by zero. (In the next problem set, you will use the same skills to build a graphing calculator.)
; An Operation is one of: ; - (make-add Number Number) ; - (make-sub Number Number) ; - (make-mul Number Number) ; - (make-div Number Number) (define-struct add [first second]) (define-struct sub [first second]) (define-struct mul [first second]) (define-struct div [first second])
Exercise 10. Design a function called result that takes an Operation and computes its result, a number.
Exercise 11. Design a function called all-results that takes a list of Operations and computes all their results, producing a list of numbers. Use map.
Unfortunately, if result gets an input like (make-div 3 0), it encounters an error and returns no result. Worse, if all-results gets an input that contains (make-div 3 0) anywhere, it encounters an error and returns no result whatsoever. Let’s safeguard against such bad inputs.
; andmap : {X} [X -> Boolean] [ListOf X] -> Boolean ; determines whether p holds for every item on lx ; (andmap p (list x-1 ... x-n)) == (and (p x-1) ... (p x-n)) (define (andmap p lx) ...)
Exercise 13. Design a function called remove-bad that takes a list of Operations and returns the list of every Operation in the list that does not divide by zero. Use filter.
Exercise 14. Design a function called all-good-results that takes a list of Operations and returns the result of every Operation in the list that does not divide by zero. Just use all-results and remove-bad.
5 build-list
(build-list 10 sqr) (build-list 10 (lambda (x) x)) (build-list 10 add1) (build-list 10 (lambda (x) (+ 1 x))) (build-list 10 (lambda (x) 1)) (build-list 5 (lambda (x) (/ x 10)))
Hint: Study the signature and purpose of build-list in Figure 95 of the textbook. There, N means NaturalNumber. But what is X?
(check-expect (evens-first 4) (list 0 2 4 6)) (check-expect (evens-first 7) (list 0 2 4 6 8 10 12))
Hint: Study the signature and purpose of build-list in Figure 95 of the textbook. What is X? Before you define the helper function to pass to build-list, remember to write down its signature, purpose, and examples.
(build-list 10 (lambda (x) (cond [(= x 3) 1] [else 0]))) (build-list 10 (lambda (x) (cond [(= x 4) 1] [else 0]))) (build-list 10 (lambda (x) (= x 5)))
(check-expect (diagonal 3) (list (list 1 0 0) (list 0 1 0) (list 0 0 1))) (check-expect (diagonal 10) (list (list 1 0 0 0 0 0 0 0 0 0) (list 0 1 0 0 0 0 0 0 0 0) (list 0 0 1 0 0 0 0 0 0 0) (list 0 0 0 1 0 0 0 0 0 0) (list 0 0 0 0 1 0 0 0 0 0) (list 0 0 0 0 0 1 0 0 0 0) (list 0 0 0 0 0 0 1 0 0 0) (list 0 0 0 0 0 0 0 1 0 0) (list 0 0 0 0 0 0 0 0 1 0) (list 0 0 0 0 0 0 0 0 0 1)))
Hint: What is X?