Download the accompanying zip file from Blackboard. Solve each problem below using Scheme on the cs-parallel server. Do not use “set!” or “set-car!” or “set-cdr!” except where it is explicitly stated that these are permitted. Do not modify the provided function signatures or file names. Test your functions using the examples in the provided zip file; you are encouraged to also create some additional examples to test more thoroughly. When you are ready to submit, compress your solution files into a zip file, and upload to Blackboard. Double-check that you have submitted all the files you intended.
1. (fetchall x L) takes key value x and list L of pairs, and returns the list of values associated with key x. Example: (fetchall ‘b ‘((a . 1) (b . 2) (c . 3) (b . 4) (a . 5) (c . 6) (b . 7) (b . 8) (d . 9))) returns (2 4 7 8).
2. (type x) takes an expression x and returns an expression with the same structure as x, except each number is replaced by ¡®num, each symbol is replaced by ¡®sym, and each Boolean is replaced by ¡®bool. Example: (type ‘(2 a #t (3 b (4 . #f) c) (5 d . 6))) returns (num sym bool (num sym (num . bool) sym) (num sym . num)).
3. (cr x y) takes list x which contains only symbols ¡®a and ¡®d, and applies the corresponding sequence of car¡¯s and cdr¡¯s to expression y. Examples: (cr ‘(a d d a d) ‘(1 (2 3 (4 5) 6) (7 8) 9)) returns (4 5), and (cr ‘(d a d d a) ‘((1 (2 3) (4 5 (6 7)) 8) 9)) returns (5 (6 7)). Thus (cr ‘(a d d a d) y) would be the same as (caddadr y) on any Scheme system that provides such a function, and
(cr ‘(d a d d a) y) would be the same as (cdaddar y).
4. These three related functions evaluate lists that represent arithmetic expressions.
a. (e1 x) evaluates a list x that might contain integers and operators + and -. Example:
(e1 ‘(10 – 6 + 15)) returns 19.
b. (e2 x) simplifies a list x that might contain integers and operators + and – and *, by
performingallthe*operations. Example: (e2′(10-2*3+5*1*3))returns(10-6+15).
c. (e3 x) evaluates a list x that might contain integers, operators + and – and *, and nested
subexpressions. Example: (e3 ‘(10-2*(7-4) + (6-(2-1))*(9-8)*(2 + 1))) returns 19.
5. These four related functions use lists to represent vectors, and nested lists to represent matrices.
a. (vv f g x y) returns the vector dot product of lists x and y when f is + and g is*, but italso
generalizes to other binary operations. Examples: (vv + * ‘(1 2 3) ‘(4 5 6)) returns 32,
and (vv min + ‘(3 5 8) ‘(7 4 2)) returns 9.
b. (vm f g x y) returns the vector-matrix product of x and y when f is + and g is *, but it also
generalizes to other binary operations. Examples: (vm + * ‘(1 2 3) ‘((1 2) (3 4) (5 6)))
returns (22 28), and (vm * min ‘(7 5 3) ‘((1 9) (4 6) (7 2))) returns (12 70).
c. (mv f g x y) returns the matrix-vector product of x and y when f is + and g is *, but it also
generalizes to other binary operations. Examples: (mv + * ‘((1 2) (3 4) (5 6)) ‘(7 8))
returns (23 53 83), and (mv * min ‘((2 9) (4 6) (7 3) (10 11)) ‘(5 8)) returns (16 24 15 40).
d. (mm f g x y) returns the matrix product of x and y when f is + and g is *, but it also generalizes
to other binary operations. Examples: (mm + * ‘((1 2 3) (4 5 6)) ‘((1 2) (3 4) (5 6))) returns ((22 28) (49 64)), and (mm*+ ‘((1 2 3) (4 5 6)) ‘((1 2) (3 4) (5 6))) returns ((80 162) (440 648)).
6. (BST) returns a new function that implements a binary search tree ADT and that behaves as shown in the example below. The new function that is returned takes two parameters: the first denotes an operation (¡®add! or ¡®search), and the second denotes a key value. Each node of the tree is represented as a list of length 3 with the format (key-value left-subtree right-subtree). The ¡®add! operation inserts the new key value into the BST, and returns the resulting tree. The ¡®search operation returns the search path as a list. See the example below for details. You are permitted to use ¡°set!¡± and ¡°set-car!¡± and ¡°set-cdr!¡± for this problem only.
Example: (define T1 (BST)) (T1 ‘add! 40)
(T1 ‘add! 20)
(T1 ‘add! 60)
(T1 ‘add! 10)
(T1 ‘add! 30)
(T1 ‘add! 50)
(T1 ‘add! 70)
; returns (40 nil nil)
; returns (40 (20 nil nil) nil)
; returns (40 (20 nil nil) (60 nil nil))
; returns (40 (20 (10 nil nil) nil) (60 nil nil))
; returns (40 (20 (10 nil nil) (30 nil nil)) (60 nil nil))
; returns (40 (20 (10 nil nil) (30 nil nil)) (60 (50 nil nil) nil))
; returns (40 (20 (10 nil nil) (30 nil nil)) (60 (50 nil nil) (70 nil nil)))
(T1 ‘search 10) (T1 ‘search 20) (T1 ‘search 25) (T1 ‘search 30) (T1 ‘search 40) (T1 ‘search 50) (T1 ‘search 55) (T1 ‘search 60) (T1 ‘search 70)
; returns (40 20 10)
; returns (40 20)
; returns (40 20 30 nil) ; returns (40 20 30)
; returns (40)
; returns (40 60 50)
; returns (40 60 50 nil) ; returns (40 60)
; returns (40 60 70)
40
20
60
10
30
50
70