One thing you have to master in learning Scheme or Lisp is how to construct s-expressions. In the following table, the first column lists some s-expressions we would like to construct. Complete the rest of the table by giving the simplest possible expression to build the s-expression.
The expression in the second column should only use the cons function and the one in the third should only use list. If it's not possible to construct an s-expression say so. You are not permitted to include a quoted list (like '(b c)) in giving you answer, including a quoted empty list -- use null for that. You are permitted, of course to use quoted atoms.
We've done the first row for you as an example. You should, of course, verify your work using the Scheme interpreter.
| Expression | Using cons | Using list | |
|---|---|---|---|
| 1.ex | (A) | (cons 'A null) | (list 'A) |
| 1.a | (A B) | ||
| 1.b | ((A B)) | ||
| 1.c | (A (B)) | ||
| 1.d | (((A)) (B)) | ||
| 1.e | (A (B) ((C))) |
Another thing you have to master in learning Scheme and Lisp is how to access elements in an s-expression. In the following table, the first column lists some s-expressions containing a single instance of the atom X. Assume that the variable S is bound to the s-expression in the first column. The second column should be an expression that when evaluated returns the atom X. You are only allowed to use the functions car and cdr and a single instance of the variable s. We've done the first row for you as an example. You should, of course, verify your work using the Scheme interpreter. In doing so, you can assign s a value using the define function, e.g., do (define s '(x)) when checking your answer for 2.ex.
| S | Expression to return the atom x | |
|---|---|---|
| 2.ex | (x) | (car s) |
| 2.a | ((1) x 2 ) | |
| 2.b | (1 (x) 2) | |
| 2.c | (1 2 (x)) | |
| 2.d | (1 (2 x)) | |
| 2.e | ((1) (2) (x) (3)) |
Write functions shiftLeft and shiftRight that take a single argument that is assumed to be a list, possibly empty. shiftLeft and returns a new list like its argument but with first element moved to the end of the list. shiftRight returns a new list with the last element moved to the front. Here are some examples:
> (shift-left '(1 2 3))
(2 3 1)
> (shift-left '(1))
(1)
> (shift-left '())
()
> (shift-left (shift-left '(1 2 3)))
(3 1 2)
> (shift-right '(1 2 3))
(3 1 2)
> (shift-right '(1))
(1)
> (shift-right '())
()
> (shift-right (shift-right '(a b c)))
(b c a)
Define the procedure count, which takes two s-expressions, and counts the number of times the first s-expression occurs in the second. Use recursion for this problem.
>(count 7 '(1 7 2 8 4 7 0 7))
3
>(count '(1 2) '((1 3) 1 2 (1 2) (1 2)))
2
Write a function named reciprocate that takes in a list of numbers, and using the map function, returns a list of reciprocals of each number.
Remember the recepirocal of a number x is equal to 1/x.
Write a function named divideAll that takes in a list of numbers, and using a combination of apply and filter returns the result of dividing all the non-zero numbers
For example, if you were passed a list containing 6 0 1 2 0 3, the answer would be 1 (6 / 1 = 6 / 2 = 3 / 3 = 1).
Describe in a sentence or two what the following function does and what kind of argument it should be called with to avoid getting a run time error.
(define conundrum (lambda (x y)
(cond ((null? y) -1)
((equal? x (car y)) 0)
(else (let ((z (conundrum x (cdr y))))
(if (< z 0) z (+ 1 z)))))))
To load a file of Scheme code the command is load. After calling this with your file, you can test your functions. For example to test your answer to (3b):
$mzscheme Welcome to MzScheme v4.1.1 [3m], Copyright (c) 2004-2008 PLT Scheme Inc. >(load "hw5.scm") >(count 7 '(1 7 2 8 4 7 0 7)) 3
Your homework should be done on the GL systems. For question numbers 1, 2, and 5, submit a text file named hw5.txt. For the other questions, place your answers in hw5.scm.
Submit your homework using the following command:
submit cs331_bwilk1 hw5 hw5.txt hw5.scm
Please test out the submission command before the due date. If you have any problems submitting, email me.