Lab 6 Creating Abstractions
Purpose: In this lab we will practice recognizing similarities in function definitions and in data definitions and how to avoid them.
Textbook References: Chapter 14: Similarities Everywhere, Chapter 15: Designing Abstractions
Abstraction
Goals: Practice using abstraction.
; A [List-of X] is one of: ; - '() ; - (cons X [List-of X]) ; lon-add2 : [List-of Number] -> [List-of Number] ; Add two (2) to each element of the given list of numbers (define (lon-add2 lon) (cond [(empty? lon) '()] [else (cons (+ (first lon) 2) (lon-add2 (rest lon)))])) ; lon-add5 : [List-of Number] -> [List-of Number] ; Add five (5) to each element of the given list of numbers (define (lon-add5 lon) (cond [(empty? lon) '()] [else (cons (+ (first lon) 5) (lon-add5 (rest lon)))]))
Sample Problem Design a function named lon-add-n that abstracts both of the functions above by taking an extra argument, which is the number to be added to each element.
; lon-add-n : [List-of Number] Number -> [List-of Number] ; Add n to each element in the list (define (lon-add-n alon n) (cond [(empty? alon) '()] [else (cons (+ (first alon) n) (lon-add-n (rest alon) n))])) (check-expect (lon-add-n '() 2) '()) (check-expect (lon-add-n '(7 16 0 18 7 7 13) 6) '(13 22 6 24 13 13 19))
Sample Problem Rewrite both lon-add2 and lon-add5 using your more general function.
; lon-add2 : [List-of Number] -> [List-of Number] ; Add two (2) to each element of the given list of numbers (define (lon-add2 alon) (lon-add-n alon 2)) (check-expect (lon-add2 '()) '()) (check-expect (lon-add2 '(16 5 1 16 2 5 0)) '(18 7 3 18 4 7 2)) ; lon-add5 : [List-of Number] -> [List-of Number] ; Add five (5) to each element of the given list of numbers (define (lon-add5 alon) (lon-add-n alon 5)) (check-expect (lon-add5 '()) '()) (check-expect (lon-add5 '(8 12 8 6 9 12 14)) '(13 17 13 11 14 17 19))
Exercise 1 Design a function starts-with-cat that consumes a [List-of String] and constructs a list of those strings that start with "cat". For example, (starts-with-cat (list "oboe" "cataract" "ox" "catharsis")) should produce (list "cataract" "catharsis").
Exercise 2 Design a function starts-with-dog that consumes a [List-of String] and constructs a list of those strings that start with "dog".
Exercise 3 Design a function starts-with that abstracts both of the functions above, taking an extra argument, which is the substring to be found in each element.
Note: to avoid "index out of range" errors you might want to ensure the prefix is shorter than the string you are checking against.
Exercise 4 Rewrite both starts-with-cat and starts-with-dog using your more general function. Write a few tests for each to be sure they work as expected.
Exercise 5 Design a function posns-in-range which takes a [List-of Posn] and two Numbers x and y and produces a list of all the posns with an x-coordinate less than x and a y-coordinate less than y.
; A CannedGood is a (make-can String Nat Nat) (define-struct can (contents month year)) ; - where contents is the contents of the can ; - month is the month when the can expires ; - and year is the year when the can expires
Exercise 6 Design a function good-cans which takes a [List-of CannedGood] and two numbers (a month and year) and returns a list of all the cans which expire AFTER the given date.
Exercise 7 Notice the similarities between in-range and good-cans? Design a function that abstracts these two functions. Use this to rewrite in-range and good-cans.
Exercise 8 Design a function any-the-same? which takes a [List-of Posn] and a Posn and produces true if any of the posns are the same as the given posn.
Exercise 9 Design a function any-starts-with? which takes a [List-of String] and a String and returns true if any of the strings in the list start with the given string.
Exercise 10 Abstract the functions any-the-same? and any-starts-with? and then use the abstraction to rewrite these two functions.
; A Restaurant is a (make-restaurant String String Nat) (define-struct restaurant (name type rating)) ; - where name is the name of the restaurant ; - type is the type of food served at the restaurant ; - and rating is the restaurant's rating (on a scale from 1 to 5)
Exercise 11 Design the function all-great? which takes a [List-of Restaurant] and a Number and determines if all the restaurants have a rating of at least that number.
Exercise 12 Design the function all-start-with? which takes a [List-of String] and a String and determines if all the strings in the list start with the given string.
Exercise 13 Abstract the functions all-great? and all-start-with? and then use the abstraction to rewrite these two functions.
Arithmetic Sequences
; A FiniteIncreasingArithmeticSequence (FIAS) is a (make-fias Number Number PositiveNumber) (define-struct fias (min max step)) ; where (make-fias min max step) is the arithmetic sequence containing all numbers of the ; form n=min+k*step such that n < max
Exercise 14 Design a function increment that consumes a FIAS and changes it’s minimum value to be the sum of the step and the original minimum value.
Exercise 15 Design a function empty-fias? that consumes a FIAS and returns true if there are no values in the sequence.
Exercise 16 Design the function fias-first which consumes a FIAS and returns the first number in the sequence. If there are no numbers in the sequence, you may produce an error.
Exercise 17 Design the function fias-rest which consumes a FIAS and returns the same sequence but without the first number. If the sequence has no numbers, you may produce an error.
Exercise 18 Develop a template for a function that consumes a FIAS using empty-fias?, fias-first, and fias-rest.
Exercise 19 Design the function add-up-sequence which consumes a FIAS and uses the template you developed in the last exercise to add up all the numbers in the sequence.
Exercise 20 Design the function add-up-all which consumes some type of data X and three functions, with the signatures [X -> Boolean], [X -> Number], and [X -> X]. The function adds up all the numbers in X using these three functions. You should treat them as you would treat empty?, first, and rest.
Exercise 21 Use add-up-all to rewrite add-up-sequence.
Exercise 22 Use add-up-lon that consumes a [List-of Number] and uses add-up-all to add up all the numbers in the list.
Before you go...
If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.