All of these problems should be done without using side effects (i.e. redefining variables or using set!) and without using any explicit Scheme looping constructs (do). Be sure to test your functions on various cases, including empty lists, simple lists with no sublists, complex lists, etc.
Your code should include your name and other identifying information as comments.
1. Suppose we enter the following definitions at the top-level of a Scheme environment:
(define x 3) (define y 7) (define z 12)
What are the results when you evaluate the following expressions starting with just the above definitions?
(let ((x 0)
(z (* x z)))
(+ x y z))(let ((x 2)
(y (- x 4))
(z (* y 2)))
(+ x y z))
(let* ((x 2)
(y (- x 4))
(z (* y 2)))
(+ x y z))
2. Consider the following definitions:
(define make-thing
(lambda (thing f)
(lambda (x)
(* thing (f x)))))
(define double
(lambda (x) (+ x x)))
(define mystery (make-thing 3 double))
(a) Describe the result of evaluating (make-thing 3 double).
What is it? (Your answer should be something like "the number 17", or "a function
that adds 1 to its argument", or "a function that takes another function as
an argument and ...".) If it is a function, describe the values bound in the
closure as well as the code (expression) that is part of the function value.
(b) What is the value of (mystery 4)? Explain how you arrived
at your answer. (For full credit, your answer should explain what happens
when (mystery
4)
is evaluated, not just report an answer that you got when you used DrRacket to
evaluate these expressions.)
Write and test Scheme functions to solve the following problems. You should
save your function definitions in a single file named hw2.scm.
General hint: Take advantage of map and other higher-order
functions when appropriate.
Your solutions do not have to be tail-recursive unless the specific problem requires
it.
length.
For example,
(lengtht '(a b c)) => 3
(lengtht '((a b) (c d e)) => 2
lengtht that is tail recursive and uses
external (non-nested) auxiliary functions as neededlengtht2 that uses no additional top-level functions.
The function should still be tail-recursive, and can use any local bindings that you want.coeff is a list
of coefficients (a0 a1 a2 ... an),
then (poly x coeff) should compute the value a0 + a1*x + a2*x2
+ ... + an*xn. For full credit, the running time of
your solution should be linear in the degree of the polynomial (i.e., O(n)).You
may define additional top-level functions or not as you wish. You may
assume that the list of coefficients contains at least one item.apply-all that, when given a list of
functions and a number, will produce a list of the values of the functions
when applied to the number. For example,
(apply-all (list sqrt square cube) 4) => (2 16 64))
positive?, we can construct an "all are"
version of it for testing whether all elements of the list satisfy
the predicate. Define a procedure all-are that does this; that is,
it should be possible to use it in ways like the following:
((all-are positive?) '(1 2 3 4)) => #t
((all-are even?) '(2 4 5 6 8)) => #f
all-are takes a predicate as an argument and returns
a new function that can be applied to a list of elements
(as is done above).
In this part of the assignment, you will create some functions to manipulate expression trees, using functions similar to the binary tree functions from the previous assignment. Here are some basics about expression trees:
Consider an arithmetic expression, such as one we would write in Scheme as (+
1 (* 2 (- 3
5))). We can think of this as being a tree-like
structure with numbers at the leaves and operator symbols at the interior nodes.
+
/ \
1 *
/ \
2 -
/ \
3 5
This structure is known as an expression tree.
For this problem, you should assume that the tree is restricted as follows:
Each node in the tree can be represented by a three-element list:
(left-operand
operator right-operand)
Write and test Scheme functions to solve the following problems. You
should save all of your function definitions for this part of the assignment
in
your hw2.scm source file.
General observation (hint): Binary trees have an elegant, recursive structure. Take advantage of this to structure your code.
(make-expr left-op operator
right-op)
=> (left-op operator right-op)
(operator '(left-op operator right-op)) => operator
(left-op '(left-op operator right-op)) => left-op
(right-op '(left-op operator right-op)) => right-op4 and not (4 () ())). A few examples:
(make-expr 4 '+ 5) => (4 + 5)
(make-expr '(6 * 3) '+ '(5 - 2)) => ((6 * 3) + (5 - 2))Quoting operators like
+ when appropriate will prevent them from
being
evaluated
to
things like
#<procedure:+>.
(preorder expr-tree)
(inorder expr-tree)
(postorder expr-tree)
Test your functions by creating a few trees using nested make-expr function calls and then using these as arguments to the traversal functions.(eval-tree expr-tree)(map-leaves f expr-tree)v is replaced by the result of applying the
higher order function f to the value in the leaf node, e.g., each node
v is replaced by (f v).
Turn in a file containing your answers to the questions from Part I, your hw2.scm source file for parts II and III, and a transcript file demonstrating the results of your functions.
For the problems in part I you can use any common file format including plain text (if you are a fan of ASCII art), Word, or pdf. You can also submit a scanned document of a handwritten solution if that is convenient, as long as it is clear and legible.
For parts II and III, turn in the hw2.scm source file and a file containing the transcript of a Scheme session demonstrating the results produced by your functions for suitable test cases. This should contain enough to show that your functions work, but no more than necessary to do that. Part of your grade will be determined by the quality of the test cases you use for this. (Don't worry if there are some minor typos in the transcript - just draw a line through anything we should ignore.)