### Lab 10 Exam Practice

This is the lab for Wednesday, June 10th. There is no lab on Monday, June 8th.

Purpose: To practice everything you have learned for the upcoming exam!

### Practice Exam

We have provided a practice exam for you to work on here. Please work through these problems first. If you have additional time to practice we have provided some more problems below.

### Before You Go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.

### Extra Practice

Please note that although we try to provide a variety of problems below we cannot guarantee that these problems contain literally all the knowledge you will need for the exam. We recommend that you also take a look at the practice exam as this is the best way to get a sense of the types of questions we usually ask.

Exercise 1 Provide the signature for the following function:

(define-struct x [y]) (define-struct z [a b]) (define (func foo bar baz) (lambda (x) (+ (foo (local [(define foo (z-a bar))] foo)) (local [(define baz (make-x bar))] (string-length (z-b bar))) (baz foo))))

; A [MaybeList X] is one of: ; - [List-of [MaybeList X]] ; - X ; and represents nested lists of elements (define ML-0 '()) (define ML-STRING "hello") (define ML-NUMBER (list 1 (list 2 3) (list (list 4 (list 5)) (list 6)) 7))

Exercise 2 Define the template for a MaybeList. You may assume that the type X is not a list for the purposes of this exercise.

Exercise 3 Using list abstractions where appropriate, design the function map-nest which takes a MaybeList and a function which acts on elements of type X. It then produces a MaybeList of the same structure where the given function has been applied to each element of type X. For example, given ML-NUMBER and sqr your function should produce (list 1 (list 4 9) (list (list 16 (list 25)) (list 36)) 49).

Exercise 4 Using list abstractions where appropriate, design the function un-nest which takes a MaybeList and produces a list of all the elements of type X in the nested lists (in order). For example, given ML-NUMBER (defined above) your function should produce (list 1 2 3 4 5 6 7).

; A MathExpr is one of: ; - Number ; - Symbol ; - (list "+" MathExpr MathExpr) ; - (list "-" MathExpr MathExpr) ; - (list "*" MathExpr MathExpr) ; - (list "/" MathExpr MathExpr) ; and represents a mathematical expression: a number, a variable, or an operation on two ; mathematical expressions (define MEX-NUM 100) (define MEX-SYM 'a) (define MEX-MULTI (list "+" (list "-" 'x 10) (list "*" 5 (list "/" 'y 5)))) ; A VariablePair is a (list Symbol MathExpr) ; and represents a definition of a variable (define VP-X (list 'x (list "*" 5 7))) (define VP-Y (list 'y 'x))

Exercise 5 Define templates for the given definitions.

Note: The following problem is quite long and is therefore probably larger than the types of problems you can expect on the exam. However, it provides good practice with skills that you will need on the exam.

Exercise 6 Design the function compute which is given a MathExpr and a list of VariablePairs. The function then computes a single number which is the result of the mathematical expression. For example, given MEX-MULTI and (list VP-X VP-Y) your function should produce 60. If the expression contains undefined variables your function should produce an error (for example, trying to call compute on MEX-MULTI with an empty list of variable pairs would produce an error).

Exercise 7 Design the function fibonacci which, given a natural number n, produces the nth number in the Fibonacci sequence. For example (fibonacci 0) will produce 0 and (fibonacci 9) will produce 34.

; An Atom is one of: ; - Number ; - String ; - Boolean ; An SExpr is one of: ; - Atom ; - [List-of SExpr]

; atom? : Any -> Boolean ; Is the given data an Atom? (check-expect (atom? 4) true) (check-expect (atom? "hello") true) (check-expect (atom? false) true) (check-expect (atom? (list 1 2 3)) false) (define (atom? x) (or (number? x) (string? x) (boolean? x)))

Exercise 8 Design the function substitute. It consumes an SExpr s and two Strings, old and new. The result is like s with all occurrences of old replaced by new. Be sure to use list abstractions and lambda where appropriate.