Exam 2

This assignment is due on Monday, March 22 at 9:00pm. Submit each section using Handin as a separate assignment.

• Until you finally submit all your work on this exam, you are not allowed to consult anything other than material written before the exam is posted. For example, you may consult the Beginning Student Language reference or rewatch any videos, but you may not read the newswire or talk to any person.

• If you have a question, make a post on CampusWire that is "visible to instructors to TAs only". The course staff will post any announcements about the exam to CampusWire.

• Unless otherwise stated, you are not required to use anything particular provided by Intermediate Student with Lambda.

• If you define something, you can use it in subsequent answers in the same section.

• Remember to follow the design recipe whenever you design or write a function. In particular, every type mentioned in a signature must be introduced by a data definition, except for these well-known types: Number, Image, String, Boolean, Number, String, KeyEvent, MouseEvent, Anything, Posn, NaturalNumber, [ListOf X], [Maybe X]. It may also be helpful to design helper functions.

• If they are given to you, you do not need to write the signature and purpose statements again. Likewise, you do not need to repeat any test cases given to you, but you should add tests wherever appropriate.

• You do not need to write separate templates unless the problem explicitly asks for them. We expect that the functions you write follow the appropriate template, however.

• Some basic test taking advice: Before you start answering any problems, first read every problem, so your brain can think about the harder problems in background while you knock off the easy ones.

• The Challenge is bonus. Solve it if you want extra credits. The maximum score for the exam is 29 + 15 + 18 = 62 points. Any points you get from the challenge section (total 8) is gonna be added to your score, maxing out at 62.

1 Trees (29 points)

Here is the data definition for a binary tree of numbers. A node contains a number and some nodes have two child trees.

; A TreeOfNumbers is one of:

;  - (make-node0 Number)

;  - (make-node2 Number TreeOfNumbers TreeOfNumbers)

(define-struct node0 [value])

(define-struct node2 [value first second])

1. (3 points) Write 3 examples of TreeOfNumbers.

2. (8 points) Design a function reduce-value that subtracts a given number from the numbers in all the nodes in a TreeOfNumbers.

   ;; reduce-value : TreeOfNumbers Number -> TreeOfNumbers

   ;; subtracts a given number from all the values in a tree

3. (8 points) Design a function constant-value that takes a TreeOfNumbers and given Number and produces a new TreeOfNumbers with the same structure as the original one, but where all of the values are the given number

   ;; constant-value : TreeOfNumbers Number -> TreeOfNumbers

   ;; set all the values in a tree to the given number

4. (6 points) Abstract reduce-value and constant-value into a single function modify-value. Provide new definitions reduce-value2 and constant-value2 using modify-value.

5. (4 points) Use the abstraction modify-value to define a function double-value that doubles all the values in a TreeOfNumbers.

   ;; double-value : TreeOfNumbers -> TreeOfNumbers

   ;; returns a tree similar to input but with all values doubled

2 Getting in line (18 points)

1. (2 points) Write three examples of ListOfNumbers, one of which is not sorted from smallest to largest.

   ; A ListOfNumbers is one of:

   ;  - empty

   ;  - (cons Number ListOfNumbers)

2. (9 points) Design the function insert which takes a Number and an ListOfNumbers and puts the number in the correct place in the list, assuming the list is already sorted. The new number should go before all the numbers bigger than it, and after all the numbers smaller than it.

   ; insert : Number ListOfNumbers -> ListOfNumbers

   ; insert the number in sorted order

   (check-expect (insert 1 empty) (list 1))

   (check-expect (insert 5 (list 1 3 7 9)) (list 1 3 5 7 9))

3. (7 points) Design the function isort which takes a ListOfNumbers and produces a ListOfNumbers in sorted order.

   Hint! Use insert as a helper function, and follow the template!

   Note: You may not use the built-in sort function to define isort.

3 My dog ate the design recipe (15 points)

1. (5 points) The following function was found without a signature, purpose statement, or examples and tests. Recreate them based on the function definition.

   (define (manhattan-distance p1 p2)

   (+ (abs (- (posn-x p1) (posn-x p2)))

   (abs (- (posn-y p1) (posn-y p2)))))

2. (5 points) The following function was found without a signature, purpose statement, or examples and tests. Recreate them based on the function definition.

   (define (generate-nums n)

   (cond [(zero? n) empty]

   [else (cons (random 10) (generate-nums (sub1 n)))]))

3. (5 points) The following function was found without a signature, purpose statement, or examples and tests. Recreate them based on the function definition.

   (define (count-matches f? l)

   (cond [(empty? l) 0]

   [(f? (first l)) (+ 1 (count-matches f? (rest l)))]

   [else (count-matches f? (rest l))]))

4 Bonus Challenge: Building Built-in Abstractions (8 points)

1. (4 points) Recall the signature and purpose of map and foldr.

   ; [X Y] [X Y -> Y] Y [List-of X] -> Y

   ; applies f from right to left to each item in lx and b

   ; (foldr f b (list x-1 ... x-n)) == (f x-1 ... (f x-n b))

   (define (foldr f b lx) ...)

   ; [X Y] [X -> Y] [List-of X] -> [List-of Y]

   ; constructs a list by applying f to each item on lx

   ; (map f (list x-1 ... x-n)) == (list (f x-1) ... (f x-n))

   (define (map f lx) ...)

   Define my-map, which is like map but is defined using foldr.

2. (4 points) Recall the signature and purpose of foldl.

   ; [X Y] [X Y -> Y] Y [List-of X] -> Y

   ; applies f from left to right to each item in lx and b

   ; (foldl f b (list x-1 ... x-n)) == (f x-n ... (f x-1 b))

   (define (foldl f b lx) ...)

   (foldl + 0 '(1 2 3 4 5))

   == (+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0)))))

   == (+ 5 (+ 4 (+ 3 (+ 2 1))))

   == (+ 5 (+ 4 (+ 3 3)))

   == (+ 5 (+ 4 6))

   == (+ 5 10)

   Define the function rev, which reverses the elements of a list of numbers and is defined using foldl.

   ; rev : [List-of Number] -> [List-of Number]

   ; reverse the list

   (check-expect (rev empty) empty)

   (check-expect (rev (list 1 2 3)) (list 3 2 1))