►C211/  H211:   Introduction to Computer Science
▼Problem sets
►Problem set 8:   Abstraction
On this page:
1 Images
2 Lists
3 Non-empty lists
4 Challenges
8.6.0.14
    contents  ← prev  up  next → 

Problem set 8: Abstraction

This assignment is due on Wednesday, October 19 at 11:59pm. Submit it using Handin as assignment ps8. Corrections can be presented until Friday, November 11.

This problem set builds on the skills that we introduced in Lectures 2−9 and 11−16. To encourage you to review those lectures, your grade on this assignment will be capped by your grade on those lectures at the time you submit (or correct) this assignment. You can resubmit lecture exercises at any time.

Remember to follow the design recipe whenever you design or write a function. In particular, every type mentioned in a signature must be introduced by a data definition, except for these well-known types: Number, Image, String, Color, Boolean, KeyEvent, MouseEvent, Anything, Posn, NaturalNumber, ListOfNumbers, 1String, [ListOf X].

Note: Use the “Intermediate Student” language or the “Intermediate Student with lambda” language on this assignment.

Don't give up. Start problem sets early. Go to office hours. Go to lecture.

Recall the abstraction recipe for functions:

  1. Design at least 2 similar functions.

  2. Identify inessential differences and revise functions to remove them. (Helpers are often useful for removing inessential differences.)

  3. Circle essential differences and pick input names for each of them.

  4. Design the abstraction by replacing differences with input names. (The new abstraction should have its own signature and purpose statement. If the original tests do not provide sufficient coverage for the abstraction, include additional tests.)

  5. Redefine the original functions using the new abstraction. (You don’t need to submit the original versions.) The redefined functions should not be commented out. They should have the same signatures and purpose statements as before as well as pass the same tests as before.

Again, the new abstraction should have its own signature and purpose statement. If you merely copy a signature or purpose statement from an original function, it will be wrong. The abstraction’s signature should specify the new inputs, and the abstraction’s purpose statement should explain the new inputs. In particular, if one of the new inputs is a function such as + or *, then the abstraction’s signature should specify that function’s signature [inside square brackets], like this:
; abstraction : ... [Number Number -> Number] ... -> ...

1 Images

Recall that the 2htdp/image library provides the following:
(require 2htdp/image)
 
; A Mode is one of:
; - "outline"
; - "solid"
 
; A Color is one of:
; - "red"
; - "yellow"
; - "blue"
; - "magenta"
; - "white"
; - "black"
; - ...
 
; overlay   : Image Image              -> Image
; text      : String Number Color      -> Image
; rectangle : Number Number Mode Color -> Image
; star      : Number Mode Color        -> Image
; square    : Number Mode Color        -> Image
; triangle  : Number Mode Color        -> Image
; circle    : Number Mode Color        -> Image

Exercise 1. Abstract from the two functions below.
; notice : String -> Image
; typeset a calm notice
(check-expect (notice "This is fine")
              (overlay (text "This is fine" 20 "black")
                       (rectangle 200 100 "solid" "white")))
(define (notice s)
  (overlay (text s 20 "black")
           (rectangle 200 100 "solid" "white")))
 
; alert : String -> Image
; display a frantic alert
(check-expect (alert "It's on fire")
              (overlay (text "It's on fire" 20 "yellow")
                       (rectangle 200 100 "solid" "red")))
(define (alert s)
  (overlay (text s 20 "yellow")
           (rectangle 200 100 "solid" "red")))
Call your new abstraction sign. Again, it should have its own signature and purpose statement. Don’t forget to redefine the original functions using it.

Exercise 2. Abstract from the two functions below.
; outlined-star : Number Color Color -> Image
; draw an outlined star of the given size,
; the given stroke color, and the given fill color
(check-expect (outlined-star 30 "blue" "magenta")
              (overlay (star 30 "outline" "blue")
                       (star 30 "solid" "magenta")))
(define (outlined-star size stroke fill)
  (overlay (star size "outline" stroke)
           (star size "solid" fill)))
 
; outlined-square : Number Color Color -> Image
; draw an outlined square of the given size,
; the given stroke color, and the given fill color
(check-expect (outlined-square 50 "red" "yellow")
              (overlay (square 50 "outline" "red")
                       (square 50 "solid" "yellow")))
(define (outlined-square size stroke fill)
  (overlay (square size "outline" stroke)
           (square size "solid" fill)))
Call your new abstraction outlined. Again, it should have its own signature and purpose statement. Don’t forget to redefine the original functions using it.

2 Lists

Exercise 3. Abstract from remove-<=100 in Problem set 7: Lists and the following function:
; remove-positive : ListOfNumbers -> ListOfNumbers
; remove all positive numbers from the given list
(check-expect (remove-positive empty) empty)
(check-expect (remove-positive (list 0 1 -3 2)) (list 0 -3))
(check-expect (remove-positive (list 1 -3 2)) (list -3))
(define (remove-positive lon)
  (cond [(empty? lon) empty]
        [(positive? (first lon)) (remove-positive (rest lon))]
        [else (cons (first lon) (remove-positive (rest lon)))]))
Call your new abstraction rid. Again, it should have its own signature and purpose statement. Don’t forget to redefine the original functions using it.

Exercise 4. Use your new abstraction rid to design a function remove-multiples-of-3 that takes a list of numbers and removes all numbers divisible by 3.

Exercise 5. 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 [(= n 0) (list (sin 0))]
        [else (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 [(= n 0) (list (sqrt 0))]
        [else (cons (sqrt n) (tab-sqrt (sub1 n)))]))

Exercise 6. Abstract from tab-sin and tab-sqrt. Call your new abstraction tabulate. Again, it should have its own signature and purpose statement. Don’t forget to redefine the original functions using it.

Exercise 7. Use your new abstraction tabulate to design a function tab-sqr that tabulates sqr between the input n and 0 (inclusive) in a list.

3 Non-empty lists

Here is the data definition for a non-empty list of Strings:
;; A NEListOfStrings is one of:
;; - (cons String empty)
;; - (cons String NEListOfStrings)
And here is the data definition for a non-empty list of Images:
;; A NEListOfImages is one of:
;; - (cons Image empty)
;; - (cons Image NEListOfImages)
Because the data definitions for a non-empty list are different from the data definitions for a list, the templates for processing a non-empty list are also different from the templates for processing a list. In this section, follow the templates for processing a non-empty list.

Exercise 8. Write down the template for processing a NEListOfStrings. Make it look like a function called process-nelos, and do not put it in a comment. Hint: If you need a refresher about writing processing templates, review Lecture 12: Unlimited data Exercise 3. As usual, because the data definition says “one of” two cases, the template should be cond with two cases. Each of the two cond questions should pick out one of the two cases depicted in the data definition.

Exercise 9. Design a function commas that takes a non-empty list of strings as input and joins them into a single string, adding commas in between. For example, (commas (list "water" "yeast" "flour")) should produce the string "water,yeast,flour".

Exercise 10. Design a function beside-all that takes a non-empty list of images as input and joins them into a single image, as a horizontal row beside each other.

Exercise 11. Abstract from NEListOfStrings and NEListOfImages. Call your new abstraction [NEListOf X]. Don’t forget to redefine NEListOfStrings and NEListOfImages using NEListOf.

Exercise 12. Abstract from commas and beside-all. Call your new abstraction join. Again, it should have its own signature and purpose statement. Don’t forget to redefine the original functions using it.

Exercise 13. Using NEListOf and join, design a function smallest-number that takes a non-empty list of numbers as input and returns the smallest number. (If multiple numbers are equally small, return any of them.)

4 Challenges

Exercise 14. Abstract from the functions weight, lighten, and enlarge in Problem set 6: Unions and recursion.

Hint: All these functions follow the template for processing a Mobile, but they fill in the template’s dots in different ways. Introduce helper functions to reduce each difference to one word.

Exercise 15. Design a function mul-table that makes a multiplication table (a list of lists of numbers) using a given list of numbers. Here are two examples of the desired behavior:
(check-expect (mul-table empty) empty)
(check-expect (mul-table (list 2 3 5 10))
              (list (list 4 6 10 20)
                    (list 6 9 15 30)
                    (list 10 15 25 50)
                    (list 20 30 50 100)))
Do this exercise using map. Do not use recursion, cond, empty?, cons?, empty, cons, first, or rest. Hint: Use local or lambda.

    contents  ← prev  up  next →