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.
Some of the problems can be answered by just typing expressions into a Scheme interpreter and transcribing the results. Feel free to use DrScheme to check your results, but even though you might get the points, you won't learn what you need if you don't actually do the exericse.
(define lst '(a b c))
(define another '(x (y)))
(define q1 (list lst another))
(define q2 (cons lst another))
(b) What are the values of q1 and q2 if these are printed?
2. Suppose we execute the following Scheme statements (define lst '(p q r))
(define more '((a b) c))
(define app (append lst more))
(define rev (reverse more))
For each of the following, show the value that results from evaluating the given expression.
(a) (cdr lst)
(b) (cddr lst)
(c) (cadr more)
(d) app
(e) rev
(f) (cons more rev)
Write and test Scheme functions to solve the following problems. In some cases
you may find it useful to write additional helper functions besides just the
functions requested. You
should save all of your function definitions in a single source file. In
DrScheme you can use File->Save definitions as to create
a file that contains your function definitions.
The normal convention is to use the extension .scm to end Scheme
file names.
The number of possible combinations (subsets) of k things taken from a set of
n items is given by the formula C(n,k) = n! / (k! (n-k)!). (where ! is the
factorial function) Write a function (comb n k) to compute C(n,k). You may
use any
recursive implementation of factorial that you like.
Write a function zip that takes two lists as arguments and returns a single
list whose elements are taken alternatively from the original lists. For example, (zip
'(a b c) '(x y z)) should evaluate to
(a x b y c z). If the lists have different lengths, the remaining unpaired
elements of the longer list
should appear at the end, e.g., (zip '(1 2) '(w x y z)) should evaluate
to (1 w 2 x y z).
Write a function unzip that takes a list as an argument and returns a list
containing two lists that have alternating elements from the original list.
For example, (unzip
'(a b c d e f)) should evaluate to
((a c e) (b d f)). If the original list has an odd number of elements,
the extra element at the end may appear at the end of either of the resulting
lists.
If a list contains multiple copies of the same element in succession, the
list can often be stored more compactly using run length encoding, in which
the repeated
element is given just once, preceded by the number of times it is repeated.
Write a function expand that takes a list of elements and frequencies
and expands them into a simple list. For example, the result of (expand '(a
(3 b) (3 a) b (2 c) (3 a))
should be (a b b b a a a b c c a a a).
A binary tree can be represented as a list in many ways. One way is to represent each node in the tree as a list of three items containing the node value and left and right subtrees, with the empty list () being used to represent an empty tree or subtree. For example, () is an empty tree, (1 () ()) is a single node containing the value 1 and empty left and right subtrees, and (1 (2 () ()) (3 () ())) is a tree with root 1, a left subtree containing the value 2, and a right subtree with the value 3.
To make it easier to work with data structures in Scheme, one convention
is to define simple functions to construct and access elements of the data
structure. For a binary tree, we can define the constructor (node value
left right)
to be (list value left right). Nothing changes underneath, but we
can then use this
For this assignment, you should turn in your work both electronically over the web and on paper.
Turn in a copy of your Scheme source file from part II using this online turnin form.
Hand in the following: