All of these problems should be done without using side effects (i.e. redefining variables or using set!). Be sure to test your functions on various cases, including empty lists, simple lists with no sublists, complex lists, etc.
Suppose we enter the following definitions in at the top-level of a Scheme environment:
(define a 3) (define b 6) (define c 12) (define x (lambda (x) (+ x c))) (define y (lambda (z) (* 2 (x z))))
What are the results when you evaluate the following expressions
(let ((b 2)
(a 5))
(+ a b c))(let ((c 4)
(b (* a c)))
(+ b c))
(let* ((c 4)
(b (* a c)))
(+ b c))
(x 5)
(let ((c 2))
(x 5))(map y '(2 3 4 1))(map (lambda (z) (+ a b)) '(1 2 3))Scheme does not include classes or modules to directly support encapsulation or abstract data types, but there are common idioms for this using functions to abstract away from the underlying representation of data (usually a list).
In this part of the assignment, create some functions to manipulate binary trees and use them for some typical tree problems. The basic idea is to represent each node in a binary tree using a 3-element list:
(contents left-child
right-child)
The first element, contents, is the value stored in the
node. It can be any scheme object at all The two other list elements
are pointers to the left and right subtrees of this node, if any. If a
subtree is empty, this is indicated by using an empty list ()
as the value for left-child and/or right-child, as
appropriate.
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 a single source file.
General observation (hint): Binary trees have an elegant, recursive structure. Take advantage of this to structure your code.
(make-node value left right)
=> (value left right)
(value-of '(value left right)) => value
(left-child '(value left right)) => left
(right-child '(value left right)) => rightlist,
cons, car, and cdr. The advantage
of having these functions is that you can write other code in terms of nodes, values, and children, not car, cddadr,
and similar things.
The resulting code is usually much easier to read.(display-preorder aTree)
(display-inorder aTree)
(display-postorder aTree)
Test your functions by creating a few trees using nested make-node
function calls and then using these as arguments to the traversal functions.(is-member value aTree)#t if value appears in some node of
the tree, otherwise it should evaluate to #f. For this
problem, value
appears in the tree if it is equal? to the value stored in some
node. map-tree that has two arguments, a function and a
tree. Evaluation of(map-tree f aTree)aTree,
but whose node values are calculated by applying the function f
to the corresponding node value in the original tree.Symbolic algebra was one of the original application areas for Lisp, the ancestor of
Scheme. In this part of the assignment, write a function that solves symbolic equations in one variable.
Function solve should have two arguments: a variable var
and an equality eqn. The result of (solve var eqn)
should be another equality where var appears alone on the left and
whose right argument is the solution of the original equation in terms of that variable.
The top level of the input equation eqn should be a list of the form (=
exp1 exp2). The two expressions exp1 and exp2 should be
legal Scheme expressions formed from atoms, numbers, and function calls involving +,
-, *, and / (only). You should assume that each of these
functions is binary - has exactly two arguments. You don't need to worry about division by 0.
If there is exactly one occurrence of var in eqn, return the
solution. Otherwise, return the atom TOO-HARD. Except for checking for the
right number of occurrences of the unknown, you can assume the input is well-formed.
Test your solve function on a number of examples to demonstrate that it is
working correctly, including the following. (The answers are given on the next line in
each case.)
(solve 'x '(= 3 x)) (= x 3) (solve 'x '(= (+ x 3) (* 8 y))) (= x (- (* 8 y) 3)) (solve 'y '(= (+ (+ (* a x) (* b y)) k) 0)) (= y (/ (- (- 0 k) (* a x)) b)) (solve 'x '(= y (/ 1 x))) (= x (/ 1 y)) (solve 'x '(= (+ (+ (* a (* x x)) (* b x)) c) 0)) TOO-HARD (solve 'y '(= y (* 2 y))) TOO-HARD (solve 'x '(= (* 2 (- 3 x)) (+ y z))) (= x (- 3 (/ (+ y z) 2)))
Your solution should be written completely in a functional style -- you
may not use functions with side effects, such as set!,
set-car!, and so forth. Your code should be well-commented.
If appropriate, create "data structures" using functions,
like the ones we created for the binary tree problems in Part II. (For
example, your code could be much easier to read if you define functions to
extract the operator, left operand, and right operand from a binary expression
or equation.)
Your Scheme code for this part of the assignment in a separate file from the tree functions created in part II.
For this (as well as most) assignments, you should turn in your work both electronically over the web and on paper.
Turn in a copy of both of your Scheme source files from parts II and III using this turnin form.
Hand in the following: