On this page:
1 What is X?
2 Using local
3 Combining built-in abstractions
4 Calculator
5 build-list
8.12

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.

Do not follow the template for processing a list. Instead, when you get to design recipe step 5 for the add-six-to-all function, use the built-in list abstraction map. It is described in Figure 95 of the textbook:
; 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) ...)
What is X and what is Y?
  1. Answer in a comment:
    ; In the signature of map, X=??? and Y=???

  2. 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]

  3. 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.

Do not follow the template for processing a list. Instead, when you get to design recipe step 5 for the odd-strings-only function, use the built-in list abstraction filter. It is described in Figure 95 of the textbook:
; filter : {X} [X -> Boolean] [ListOf X] -> [ListOf X]
; produces a list from those items on lx for which p holds
(define (filter p lx) ...)
What is X?
  1. Answer in a comment:
    ; In the signature of filter, X=???

  2. 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]

  3. 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.

Exercise 3. Here’s a handy 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))))))
Using dist, design a function called near-origin that takes a list of Posns and produces a new list of only those given Posns whose distance to the origin (make-posn 0 0) is less than 5.

Do not follow the template for processing a list. Instead, when you get to design recipe step 5 for the near-origin function, use the built-in list abstraction filter. What is X?
  1. Answer in a comment:
    ; In the signature of filter, X=???

  2. 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]

  3. 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.

Do not follow the template for processing a list. Instead, when you get to design recipe step 5, use the built-in list abstraction filter. What is X?
  1. Answer in a comment:
    ; In the signature of filter, X=???

  2. Copy the signature of filter, then replace X throughout by what you guessed.

  3. 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.

Do not follow the template for processing a list. Instead, when you get to design recipe step 5, use filter. What is X?
  1. Answer in a comment:
    ; In the signature of filter, X=???

  2. Copy the signature of filter, then replace X throughout by what you guessed.

  3. 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.

Do not follow the template for processing a list. Instead, when you get to design recipe step 5, use map. What is X and what is Y?
  1. Answer in a comment:
    ; In the signature of map, X=??? and Y=???

  2. Copy the signature of map, then replace X and Y throughout by what you guessed.

  3. 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🔗

Exercise 7. Design a function lengths->3 that takes a list of strings and returns a list of numbers, which are the lengths of those strings longer than 3 characters.

Do not follow the template for processing a list. Instead, when you get to design recipe step 5, use map and filter.
  1. Answer in comments:
    ; In the signature of map, X=??? and Y=???
    ; In the signature of filter, X=???

  2. Copy the signatures of map and filter, then replace X and Y and X throughout by what you guessed.

  3. 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".

Do not follow the template for processing a list. Instead, when you get to design recipe step 5, use map and filter.
  1. Answer in comments:
    ; In the signature of map, X=??? and Y=???
    ; In the signature of filter, X=???

  2. Copy the signatures of map and filter, then replace X and Y and X throughout by what you guessed.

  3. 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 9. Design a function that takes a list of numbers and produces a new list of numbers by
  • squaring it,

  • adding 5 to it, and

  • keeping the result if it ends in either 5 or 6 in decimal.

Here’s a start:
; 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.)

Below is the data definition for an arithmetic operation:
; 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.

Exercise 12. Design a function called all-good? that takes a list of Operations and determines whether every Operation in the list does not divide by zero. Use andmap, which is described in Figure 95 of the textbook:
; 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🔗

Exercise 15. Anticipate (then determine) the values of the following expressions.
(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?

Exercise 16. Design a function evens-first that takes a natural number as input and returns the list of the first that many even numbers starting with 0.
(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.

Exercise 17. Anticipate (then determine) the values of the following expressions.
(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)))

Extra fun. Design a function diagonal that receives one input, a number, and returns a list of that many lists of 0 and 1 in the following diagonal arrangement:
(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?