Lab 11 Exam Practice
Purpose: To practice everything you have learned for the upcoming exam!
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 exams which have been posted on Piazza as these are the best way to get a sense of the types of questions we usually ask.
Exercise 1 Students have been asking us about the difference between foldr and foldl. To help them understand the difference, please design both functions without the use of list abstractions. You will need to name them my-foldr and my-foldl to avoid any name collisions with the originals.
; 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 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))))
Exercise 8 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.