|
|
In this lab you will practice operations on lists and trees.
[This is exercise 2.30 from the textbook.] Define a procedure square-tree to square the leaves of a tree. Define square-tree both directly (i.e., without using any higher-order procedures) and also by using map and recursion. square-tree should behave as follows:
(square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))) (1 (4 (9 16) 25) (36 49))
[This is exercise 2.32 from the textbook.] We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:
(define (subsets s)
(if (null? s)
(list ())
(let ((rest (subsets (cdr s))))
(append rest (map ??? rest)))))
[This is exercise 2.33 from the textbook.] Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:
(define (my-map p sequence) (accumulate (lambda (x y) ???) () sequence)) (define (my-append seq1 seq2) (accumulate cons ??? ???)) (define (my-length sequence) (accumulate ??? 0 sequence))Recall that accumulate is not predefined in Scheme, but we have included it in the template file.
Write a procedure to reverse a list. The most effecient way to do this is with a simple linear iterative procedure. It should work as follows:
(my-reverse (list 1 2 3 4)) (4 3 2 1) (my-reverse (list 1 (list 2 3) 4)) (4 (2 3) 1)
Complete exercise 2.27 from the textbook in two dfferent ways, using
recursion and using map.
This is similar to the reverse procedure you've seen in class, but
the difference is that instead of just looking at the first level
of the list and reversing those elements, you need to reverse the
elements in all of the levels of the list.
Note: The examples the book gives can be misleading. Your
procedure must be able to reverse at an arbitrary and variable depth.
For example,
(deep-reverse (list 1 2 3 4)) (4 3 2 1) (deep-reverse (list 1 (list 2 3) 4)) (4 (3 2) 1) (deep-reverse (list (list (list (list 1 2 3))))) ((((3 2 1))))
[This is exercise 2.28 from the textbook].
Write your procedure in two dfferent ways,
one without using any higher-order procedures and one using map and recursion.
Write a procedure fringe that takes as argument a tree
and returns a list whose elements are all the leaves of the tree arranged
in left-to-right order. For example,
(define x (list (list 1 2) (list 3 4))) (fringe x) (1 2 3 4) (fringe (list x x)) (1 2 3 4 1 2 3 4)
A string is a collection of characters surrounded by double quotes. An
example of a string is "hello". For this problem you should write
the procedure string-to-frequency-list. This procedure
should take in a string, and return a list of symbol-frequency
pairs. An example of symbol-frequency pair is the list (#\h
2). #\h is the symbol (remember #\h
is a character, not an actual scheme symbol), and 1 is the frequency, or
the number of times #\h appeared in some string we wanted
to encode. str2frequency-list must return a list of
these frequency pairs, one pair for each unique character in the
string passed to string-to-frequency-list.
(string-to-frequency-list "hello") should return the list:
((#\h 1) (#\e 1) (#\l 2) (#\o 1)), or a similar list with
a different ordering of the symbol-frequency pairs.
The procedure string->list is built into STk, and may be
useful to you. It takes in a string and returns the list containing
each of the characters in the string in the order they appear in the
string. So for instance (string->list "hello") would return
the list (#\h #\e #\l #\l #\o).
string-to-frequency-list is more complicated
than procedures in prior labs. Plan how to decompose the problem into
simpler problems before you start writing your procedure.
You can come up with your own solution, or follow the steps outlined here:
(unique L) which will examine a
list and return a sublist with all duplicates removed. For example
(unique (list 3 1 3 4 1)) would return a list like
(3 1 4) which has the duplicate elements removed.(member x lst) to check if x is list
lst. (count-occurrences obj L) which
will count the number of times obj appears in the list
L.= operator, but this only works for numbers. To test
if x and y are the same for more general
kinds of data you can use (eqv? x y). unique and string->list
functions.) Ideally you you will use the map function to
recurse over this list.
Use count-occurences to generate the frequencies
for each unique character during your recursive or iterative process.
The bonus will add 1 point to your lab score. It might not seem much for the work you have to do, but points will add up and you will learn much more!
Useful procedures for the bonus question:
(member obj lst) returns a
nonfalse value if obj is found in list lst or
#f otherwise. More precisely, if obj is
in the list lst it will return the list starting at
obj.(eqv? obj1 obj2) returns
#t if obj1 and obj2 are the same.
It works for numbers, characters, and symbols, but not for lists.
To compare characters you can also use (char=? char1 char2)
(string->list str)
returns a list of characters contained in string str.