EECS 111 Winter 2017 Tutorial 9 (Exam Practice)
Sarah Lim (http://sarahlim.com/eecs-111)
Q1. Scope and Mutation
In most countries, the age of majority is 18. Some countries have different laws. In Scotland, for instance, the age of majority is 16.
Suppose we want to write a program to determine whether someone is a legal adult. We'll write a global version that works for most countries, and a Scotland-specific version.
Here are three DIFFERENT versions of this program.
;; Version 1
(define age-of-majority 18)
;; number -> boolean
(define (is-adult? age)
(>= age age-of-majority))
;; number -> boolean
(define (is-adult?/scotland age)
(begin (set! age-of-majority 16)
(>= age age-of-majority)))
;; Version 2
(define age-of-majority 18)
;; number -> boolean
(define (is-adult? age)
(>= age age-of-majority))
;; number -> boolean
(define (is-adult?/scotland age)
(local [(define age-of-majority 16)]
(is-adult? age)))
;; Version 3
(define age-of-majority 18)
;; number -> boolean
(define (is-adult? age)
(>= age age-of-majority))
;; number -> boolean
(define (is-adult?/scotland age)
(local [(define age-of-majority 16)
(define (helper a)
(>= a age-of-majority))]
(helper age)))
Each of these programs will yield a different result for the following series of function calls:
(is-adult? 16)
(is-adult?/scotland 16)
(is-adult? 16)
- What will the results of each call be, for each program? (Try to answer first without running the programs.)
- Which result (and which program) is correct?
- What is the difference between the programs? (In other words, WHY does each program yield the results it does?)
- Bonus: How would you modify the incorrect versions to be correct?
Assume you can only add new code to
is-adult?/scotland
.
Q2. Imperative Programming vs. Functional Programming
-
For each of the following code snippets, fill in the placeholder with ONE expression, either
map
orfor-each
, such that the program returns the correct results.-
(define lon (list 1 2 3 4 5)) ;; ... lon ; (list 10 20 30 40 50)
-
(define-struct person [first last]) (define sood (make-person "Sara" "Sood")) (define horswill (make-person "Ian" "Horswill")) (define zhang (make-person "Haoqi" "Zhang")) (define people (list sood horswill zhang)) (person-first sood) ; "S" (person-first horswill) ; "I" (person-first zhang) ; "H"
-
(define-struct person [first last]) (define sood (make-person "Sara" "Sood")) (define horswill (make-person "Ian" "Horswill")) (define zhang (make-person "Haoqi" "Zhang")) (define people (list sood horswill zhang)) (filter (lambda (p) (string=? (person-first p) "I")) ;; ... ) ;; (list (make-person "I" "Horswill"))
-
-
For each of the snippets above, could you produce a working solution by changing
map
tofor-each
or vice versa?
Q3. Iteration vs. Recursion
Here is a recursive implementation of a function to compute the product of a list of numbers:
;; (listof number) -> number
(define (product lon)
(cond [(empty? lon) 1]
[else (* (first lon)
(product (rest lon)))]))
As you've probably seen, there are lots of different ways to implement the same list operation, especially using imperative programming.
The purpose of this section is to help you develop a better intuition for WHY each of these strategies works, by implementing product
in various ways.
Fill out the ...
in each snippet. Each ...
is either a single keyword (e.g. if
, unless
, begin
, etc.) or a single expression.
-
Iterative Recursion
- List: argument
- Result: argument
- Helper function returns: number
(define (product lon) (local [; (listof number) number -> number (define (loop remaining result) (if (empty? remaining) ... (... (rest remaining) (* (first remaining) result))))] ...))
-
Separate result variable
- List: argument
- Result: variable
- Helper function returns: number
(define (product lon) (local [(define result ...) ;; (listof number) -> number (define (loop remaining) (if (empty? remaining) ... (begin ... (loop (rest remaining)))))] ...))
-
Separate result variable AND void helper
- List: argument
- Result: variable
- Helper function returns: void
(define (product lon) (local [(define result ...) ;; (listof number) -> void (define (loop remaining) (unless (empty? remaining) (begin ... (loop (rest remaining)))))] ...))
-
Separate result AND list variables; void helper
- List: variable
- Result: variable
- Helper function returns: void
(define (product lon) (local [(define remaining ...) (define result ...) ;; -> void (define (loop) (unless (empty? remaining) (begin ... ... (loop))))] ...))
-
Using
for-each
(define (product lon) (local [...] (... (for-each (lambda (n) ...) lon) ...)))
-
BONUS: Implement the following function, using each of the constraints in the previous five steps.
;; longest : (listof string) -> number
;; returns the length of the longest string in the list
apply
vs. foldl
Q4. - Recall this question from a previous assignment:
Write a recursive function,
depth-tree
, that returns the number of levels of nesting in aListTree
.;; depth-tree : ListTree -> number
For instance,
(depth-tree 1) ;; => 0, it's not even a list (depth-tree (list 1 2)) ;; => 1 (depth-tree (list (list 1) 7 (list 1 4 2))) ;; => 2
You probably implemented this function using foldl
. Rewrite it using apply
.
- In general, you can use
apply
andfold(l/r)
for the same categories of problems (consolidating a list into a single object using some combiner function).
For instance:
(foldl + 0 (list 1 2 3 4))
(apply + (list 1 2 3 4))
(foldr string-append "" (list "a" "b" "c" "d"))
(apply string-append (list "a" "b" "c" "d"))
Come up with a usage example for apply
that does NOT work for fold(l/r)
.
Hint: (require 2htdp/image)
Q5. Inheritance
;; Note: you'll need to
(require cs111/define-struct)
;; for this exercise.
Consider the following inheritance hierarchy:
Animal
__|___
| |
Dog Cat
- Implement the following structs:
;; An Animal is an ABSTRACT base type.
;;
;; Properties:
;; - name, a string
;;
;; Methods:
;; - greet : -> string, returns "hi, I am <name>"
;; A Cat is a subtype of Animal.
;;
;; Properties:
;; - favorite-fish, one of "tuna" "mackerel" "sardine"
;;
;; Methods:
;; - greet : -> string, returns
;; "meow, I am <name> and my favorite fish is <favorite-fish>"
;; A Dog is a subtype of Animal.
;;
;; Properties:
;; - favorite-game, one of "fetch" "agility" "nap"
;;
;; Methods:
;; - greet : -> string, returns
;; "woof, I am <name> and my favorite game is <favorite-game>"
-
Define the following variables:
-
A cat named "Peaches" whose favorite fish is "tuna"
(define peaches ...)
-
A cat named "Tubbs" whose favorite fish is "mackerel"
(define tubbs ...)
-
A dog named "Jake" whose favorite game is "nap"
(define jake ...)
-
-
Now change every animal's favorite (food/game), and change all of their names too.