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

Hand-in Server

Goals: Show the world your true beauty.

Exercise 1 Upload a picture of yourself to the handin-server.

Finite Increasing Arithmetic Sequences

Goals: Use abstraction in an unfamiliar context.

Starter Code: Below is the data definition of a finite increasing arithmetic sequence.

; 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 2 Design a function which sums the elements of a FIAS.

Exercise 3 Design a function which multiplies the elements of a FIAS. Hint: the product of an empty sequence is 1.

Exercise 4 Design a function which lists the elements of a FIAS.

Exercise 5 All of these functions look marvelously similar; abstract them, redefine them with your new function, and ensure all of your tests still pass.

Exercise 6 Design a function which determines if any element of a FIAS is a perfect square. Hint: integer?.

Exercise 7 Design a function which determines if any element of a FIAS is even.

Exercise 8 Both of these functions look marvelously similar; abstract them, redefine them with your new function, and ensure all of your tests still pass.

Abstracting Functions

Goals: Practice abstracting functions into useful abstractions.

; keep-if-greater-than-10 : [List-of Number] -> [List-of Number]

; Keeps all elements of the list greater than 10

(define (keep-if-greater-than-10 lon)

(cond [(empty? lon) '()]

[(cons? lon)

(if (> (first lon) 10)

(cons (first lon) (keep-if-greater-than-10 (rest lon)))

(keep-if-greater-than-10 (rest lon)))]))

(check-expect (keep-if-greater-than-10 '()) '())

(check-expect (keep-if-greater-than-10 (list 1 10 100 -1)) (list 100))

; keep-if-only-letters: [List-of String] -> [List-of String]

; Keeps all elements that only have letters in the string

(define (keep-if-only-letters los)

(cond [(empty? los) '()]

[(cons? los)

(if (string-alphabetic? (first los))

(cons (first los) (only-letters (rest los)))

(keep-if-only-letters (rest los)))]))

(check-expect (keep-if-only-letters '()) '())

(check-expect (keep-if-only-letters (list "abc" "12a" "ui" "989")) (list "abc" "ui"))

Exercise 10 Rewrite the two functions using the new abstraction.

; are-any-even? : [List-of Number] -> Boolean

; Are any of the numbers even?

(define (are-any-even? lon)

(cond [(empty? lon) #f]

[(cons? lon)

(or (even? (first lon))

(are-any-even? (rest lon)))]))

(check-expect (are-any-even? '()) #f)

(check-expect (are-any-even? (list 1 10 100 -1)) #t)

(check-expect (are-any-even? (list 1 15 -23)) #f)

; are-any-only-lowercase?: [List-of String] -> Boolean

; Are any strings in the list only lowercase?

(define (are-any-only-lowercase? los)

(cond [(empty? los) #f]

[(cons? los)

(or (string-lower-case? (first los))

(are-any-only-lowercase? (rest los)))]))

(check-expect (are-any-only-lowercase? '()) #f)

(check-expect (are-any-only-lowercase? (list "abc" "12a" "ui" "989")) #t)

(check-expect (are-any-only-lowercase? (list "ABC" "CDE" "fgH")) #f)

Exercise 12 Rewrite the two functions using the new abstraction.

You might have noticed that these two abstractions seem really useful when working with lists. These are so convenient that ISL actually provides these for you, just as it provides lists themselves. In ISL, these functions are called filter and ormap. There are many other ones as well, such as foldr, map, and andmap. (We’ve seen one of these in class already — which one?) These all are helpful when working with lists, since they allow you to focus how to manipulate each element of the list, while they handle the list structure itself.

That being said, they all serve distinct purposes. For instance, even though filter and ormap both take in a boolean-valued function as an operator, they use it differently: it would not make sense to use an ormap when if you wanted to keep all elements of a list that pass that boolean function, and it would not make sense to use filter if you just wanted to check if anything passed that function!

List Abstractions

Exercise 13 Provide examples and templates for the above data definitions.

Exercise 14 Use ormap to design a function that takes a [List-of Shape] and determines if any of then are "green".

Exercise 15 Use filter to design a function that takes a [List-of Shape] and keeps only circles.

Exercise 16 Use map to design a function that takes a [List-of Shape] and outputs their colors.

Exercise 17 Use foldr to design a function that takes a [List-of Shape] and stacks all of its images vertically.

Signature Detective

Goals: Practice understanding what the data type restrictions on code must be when reading it.

Exercise 18 Determine the signature for the following functions.

(define (a supercut of us)

(+ of

(if (empty? supercut)

(us #f)

(us (first supercut)))))

(define (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 ""]))