5 Designing With Lists and Abstractions
Purpose: This lab focuses on designing programs on lists, as well as creating abstractions.
Textbook references:
Part II: Arbitrarily Large Data
Chapter 14: Similarities Everywhere
Chapter 15: Designing Abstractions
Finite Increasing Arithmetic Sequences
Goals: Use abstraction in an unfamiliar context.
Starter Code: Below is the data definition of a finite increasing arithmetic sequence.
; A FIAS (Finite Increasing Arithmetic Sequence) is a: ; (make-fias Number Number Positive) (define-struct fias [min max step]) ; where (make-fias min max step) represents all numbers ; of the form min+k*step, where k is a natural number, ; such that min+k*step < max. (define fias-empty (make-fias 1 1 0.25)) ; empty sequence, as min >= max (define fias-1 (make-fias 0 1 0.25)) ; sequence with the elements (0, .25, .5, .75) ; fias-temp : FIAS -> ? (define (fias-temp fias) (... (fias-min fias) (fias-max fias) (fias-step fias)))
Sample Problem Design a function that determines if a FIAS is empty.
; empty-fias? : FIAS -> Boolean ; determines if the given FIAS is empty (define (empty-fias? fias) (>= (fias-min fias) (fias-max fias)))
Sample Problem Design the function next-sequence, which takes a FIAS and returns a new FIAS with the same max and step. The new min will be the original FIAS’s min with its step added to it.
; next-sequence : FIAS -> FIAS ; returns a new FIAS where the min is the original FIAS's min plus its step (define (next-sequence fias) (make-fias (+ (fias-min fias) (fias-step fias)) (fias-max fias) (fias-step fias)))
Sample Problem You may have noticed that next-sequence returns the rest of a FIAS, empty-fias? determines if it is empty, and that if it is non-empty fias-min is the first element in it. Redefine your fias-temp to take advantage of this recursive structure.
; fias-temp : FIAS -> ? (define (fias-temp fias) (cond [(empty-fias? fias) ...] [else (... (fias-min fias) (fias-temp (next-sequence fias)))]))
Exercise 1 Design a function which sums the elements of a FIAS.
Exercise 2 Design a function which multiplies the elements of a FIAS. Hint: the product of an empty sequence is 1.
Exercise 3 Design a function which lists the elements of a FIAS.
Exercise 4 All of these functions look marvelously similar; abstract them, redefine them with your new function, and ensure all of your tests still pass.
Exercise 5 Design a function which determines if any element of a FIAS is a perfect square. Hint: integer?.
Exercise 6 Design a function which determines if any element of a FIAS is even.
Exercise 7 Both of these functions look marvelously similar; abstract them, redefine them with your new function, and ensure all of your tests still pass.
List Abstractions
(define-struct circl [radius mode c]) (define-struct squar [side-length mode c]) (define-struct rectangl [width height mode c]) ; A Shape is one of: ; - (make-circl Number Mode Color) ; - (make-squar Number Mode Color) ; - (make-rectangl Number Number Mode Color) ; and represents either: ; - the radius in pixels, mode, and color of a circle ; - the side length in pixels, mode, and color of a square ; - the width and height in pixels, the mode, and color of a rectangle ; A Mode is one of: ; - "solid" ; - "outline"
Exercise 8 Provide examples and templates for the above data definitions.
Exercise 9 Use foldr to design a function that takes a [List-of Shape] and stacks all of its images vertically.
Exercise 10 Use filter to design a function that takes a [List-of Shape] and keeps only circles.
Exercise 11 Use map to design a function that takes a [List-of Shape] and outputs their colors.
Exercise 12 Use ormap to design a function that takes a [List-of Shape] and determines if any of then are "green".
Signature Detective
Goals: Practice understanding what the data type restrictions on code must be when reading it.
Exercise 13 Determine the signature for the following functions.
(define (a supercut of us) (+ of (if (empty? supercut) (us #f) (us (first supercut))))) (define (the moments i play in the dark) (play (in (play the dark)) (play moments i))) (define (come home to my heart) (cond [(home my) (to heart)] [(my heart) " "] [else ""]))