Lab 12: Review for the final exam

You may submit this lab to lab12 on Handin (this is optional).

Note: Whenever you write a function in this class, follow the design recipe. You will be graded accordingly. Note that choosing a built-in abstraction takes the place of the template step (Step 4).

1 Recursive unions

Exercise 1. A tree of Booleans is either a leaf containing a Boolean or a node containing two trees of Booleans (a left subtree and a right subtree). Write a data definition for TreeOfBooleans and the corresponding structure definitions. Call a leaf leaf and its unique field data, and call a node node and its two fields left and right.

Exercise 2. Write the template for processing a TreeOfBooleans.

Exercise 3. By “flipping a Boolean”, we mean replacing true with false and false with true. Write a function flip which takes a TreeOfBooleans and flips the data stored in its leaves.

Exercise 4. Write a function contains-true? which takes a TreeOfBooleans and returns true if and only if it contains a leaf storing true.

2 Data definition abstraction

Exercise 5. A tree of Strings is either a leaf containing a String or a node containing two trees of Strings (a left subtree and a right subtree). Write a data definition for trees of Strings using the structure definitions leaf and node.

Exercise 6. Write a data definition for a [TreeOf X] by abstracting over trees of Strings and trees of Booleans.

Exercise 7. Write the template for processing a [TreeOf X].

Exercise 8. Design a function tree-height which takes a [TreeOf X] and returns its height. A leaf has height 0. The height of a node is one plus the height of its taller subtree. You may find max useful.

3 Function abstraction

Exercise 9. Design a function sum-of-evens which takes a list of numbers and returns the sum of the even numbers in the input list. Use the template for processing a list.

Exercise 10. Add the following code to your definitions window:

(require 2htdp/image)

(define width 300)

(define height 400)

(define background (empty-scene width height))

Design a function draw-posns which takes a list of Posns and draws only those Posns which are within the boundaries of background. Use the template for processing a list.

Exercise 11. Abstract over sum-of-evens and draw-posns. Call your abstraction combine-some. Redefine sum-of-evens and draw-posns using combine-some.

Exercise 12. Design a function count-non-empty which takes a list of strings and returns how many non-empty strings it contains. Use combine-some.

4 Built-in abstractions

Download this recent version of the invaders code.

Exercise 13. The draw-invaders function is designed using the template for processing a list. Redefine draw-invaders using a built-in abstraction instead.

Exercise 14. The remove-invaders function is designed using the template for processing a list. Redefine remove-invaders using a built-in abstraction instead.

Exercise 15. The move-invaders function is designed using the template for processing a list. Redefine move-invaders using a built-in abstraction instead.

Exercise 16. The gen-invaders function is designed using the template for processing a natural number. Redefine gen-invaders using a built-in abstraction instead.

Exercise 17. The invaders-landed? function is designed using the template for processing a list. Redefine invaders-landed? using a built-in abstraction instead.

5 Challenges

Note: The following exercises are purely optional and more challenging than any problem on the final exam.

We’ve observed in class that foldr just “fills out the list-processing template”. We’ve also observed that the built-in list-processing abstractions can be defined using the template. In the next exercises, we’ll combine these two observations to see that foldr is the most abstract of the list-processing abstractions we have learned.

Exercise 18. Here is a renamed version of map:

; map-op : [X -> Y] [ListOf X] -> [ListOf Y]

; applies op to each element in lox

(define (map-op op lox)

(map op lox))

(check-expect (map-op string-length empty) empty)

(check-expect (map-op string-length (list "tomato" "avocado" "zucchini"))

(list 6 7 8))

Redefine map-op using foldr (instead of map). Hint: Use local.

Exercise 19. Here is a renamed version of filter:

; string-non-empty? : String -> Boolean

; checks if s is non-empty

(define (string-non-empty? s)

(positive? (string-length s)))

(check-expect (string-non-empty? "cashews") true)

(check-expect (string-non-empty? "") false)

; filter-pred : [X -> Boolean] [ListOf X] -> [ListOf X]

; keeps elements of lox which satisfy pred

(define (filter-pred pred lox)

(filter pred lox))

(check-expect (filter-pred string-non-empty? empty) empty)

(check-expect (filter-pred string-non-empty?

(list "cashews" "" "peanuts" "almonds" ""))

(list "cashews" "peanuts" "almonds"))

Redefine filter-pred using foldr (instead of filter). Hint: Use local.

Exercise 20. Here is a renamed version of ormap:

; fold-or : [X -> Boolean] [ListOf X] -> Boolean

; returns true if and only if at least one element of lox satisfies pred

(define (fold-or pred lox)

(ormap pred lox))

(check-expect (fold-or zero? empty) false)

(check-expect (fold-or zero? (list 13 2 3 0 5 0)) true)

(check-expect (fold-or zero? (list 2 3 5 7)) false)

Redefine fold-or using foldr (instead of ormap). Hint: Use local.

Exercise 21. Here is a renamed version of andmap:

; fold-and : [X -> Boolean] [ListOf X] -> Boolean

; returns true if and only if all elements of lox satisfy pred

(define (fold-and pred lox)

(andmap pred lox))

(check-expect (fold-and positive? empty) true)

(check-expect (fold-and positive? (list 13 2 3 0 5 0)) false)

(check-expect (fold-and positive? (list 2 3 5 7)) true)

Redefine fold-and using foldr (instead of andmap). Hint: Use local.