These exercises are meant for self-evaluation and practice. You need not turn in code for any of them and you are also not expected to code them all up. (Though you may find some of the functions useful in future coding.) It is sufficient if you are familiar with how to approach each of the problems. Each question is tagged with the aspect of Scheme programming that it emphasizes. More challenging questions have been marked with * (hard) or ** (darn hard).
The background materials listed on the course home page should be useful. You're almost certain to need to refer to Dybvig for some of the more esoteric Scheme features, even if you're already familiar with the basics of the language.
The history of this document: Raja Sooriamurthi wrote this problem set for C463 in the Fall of 1991. In the Fall of 1995, John Nienart updated the macro problem to reflect the changes in the Chez Scheme syntactic extensions facility, and converted the problems to HTML.
Scheme provides a primitive function
assoc that takes an
object and an alist (list of pairs) and returns the first
pair in alist whose car field is obj. If no pair in alist has obj as
#f is returned.
equal? to compare obj with the car fields of the alist.
Write a function
multi-assoc that behaves like
assoc except that it returns all the pairs in the alist
whose car field is obj.
(multi-assoc 'gee '((gee golly) (golly solly) (gee glee))) ==> ((gee golly) (gee glee)) (multi-assoc 'wed '((mon tough) (tue slog) (sat party!))) ==> #f
Write a function
filter that takes a predicate and a list
as argument and returns a list of only those elements that satisfy the
(filter odd? '(1 2 3 4 5 6 7 8 9)) ==> (1 3 5 7 9)Write
multi-associn terms of
In areas of AI like Natural Language Processing, Logic there is a need for variables which are used to represent entities (which are different from Scheme variables but similar to the algebraic notion of variables). Some of the possible notations for variables are:
The second notation is preferable for its conciseness. Write a
predicate (boolean valued function) that takes an object as input and
#t if its a variable and
otherwise. You can use either the
(variable? '*np) ==> #t (variable? "*np") ==> #f (variable? '(*np jack)) ==> #f
Write a function
explode that takes a symbol as input and
returns a list of symbols corresponding to its individual characters.
(explode 'apple) ==> (a p p l e) (explode 'a) ==> (a)
Also write a function implode that is the inverse of explode. It takes a list of one character symbols and combines them to form a single symbol.
(implode '(a p p l e)) ==> apple (implode '(a)) ==> a (implode (explode 'geewhiz)) ==> geewhiz
For simplicity you may assume that the symbols on which explode and implode operate on consist only of alphabets.
* Extend explode and implode to deal with symbols that have numerals in them.
(explode 'r2d2) ==> (r 2 d 2)
** Chez uses the notation of bracketing a symbol between two
vertical bars when the symbol contains special characters like a space
or parenthesis. For example,
|apple 2| represents an
identifier with a space between the e and 2;
represents a symbol which is flanked by a pair parenthesis.
(symbol? '|(a)|) ==> #t (symbol? '(a)) ==> #f (pair? '|(a)|) ==> #f (pair? '(a)) ==> #tGeneralize
implodeto work for lists.
(explode '(r2d2))) ==> (|(| r 2 d 2 |)|) (explode '(r2d2 c3po)) ==> (|(| r 2 d 2 | | c 3 p o |)|) (implode (explode '(r2d2 c3po))) ==> (r2d2 c3po)This is a hard problem. One solution would be to use string-ports.
Write a function
cxr that is a generalization of the
car/cdr operators provided in Scheme.
should take a string of "a"s and "d"s representing the sequence of
cdr operations to be performed and
return a function capable of performing that sequence.
(cxr "ad") is equivalent to the function
((cxr "ad") '(i ii iii iv v vi vii)) ==> ii (define sixth (cxr "addddd")) (sixth '(i ii iii iv v vi vii)) ==> vi
Write a function
split that takes a flat list of symbols
and numbers and returns a pair of lists, one consisting only of
symbols and the other only of numbers.
(split '(a 2 s 4 5 f)) ==> ((a s f) (2 4 5)) (split '()) ==> (() ())A two pass algorithm is simple. Try writing a one pass algorithm using accumulators. Re-write your solution using functional continuations.
map function available in scheme can take a
function of one argument and one list and apply that function to all
the top-level items of the list. Write a generalization of this
mu-map that can take a function of any arity and a
corresponding number of lists. It then returns a list by applying the
function to the corresponding elements of all the lists. You may
assume that all the lists are of the same length.
(mu-map (lambda (x y) (+ x y)) '(1 2 3) '(10 11 12)) ==> (11 13 15)Modify
mu-mapso that it even when the lists are not of the same length it will work. It applies the function to as many elements as there are in the shortest list.
(mu-map (lambda (x y) (+ x y)) '(1 2 3 4 5) '(10 11)) ==> (11 13)
call/ccas an escaper
Write a function
list-index that takes an object and a
list as argument and returns the zero-based index of the first
occurrence of the object in the list. You signal the absence of the
object in the list by returning -1.
(list-index 'a '(a s d a)) ==> 0 (list-index 'b '(a s d b s)) ==> 3 (list-index 'z '(a b c)) ==> -1There are several ways you can do this. You could first test to see if the object you are looking for is in the list with a function like
memberand if not you return -1 or else you proceed to determine the index. Instead of testing for membership you could use an accumulator. Finally you could use
call/ccto set up an escaping function which you then invoke when you have determined that the object is not in the list. Write the function using
Write the function
reverse that reverses the top level
elements of a list.
(reverse '(a b c d)) ==> (d c b a) (reverse '()) ==> ()Sounds easy? Well, heres the catch. You are allowed to use only
condand, of course, recursive applications of
reverse. This means no other help functions are allowed and so the general way of writing reverse with snoc as below doesn't count:
(define reverse (lambda (ls) (cond [(null? ls) '()] [else (snoc (reverse (cdr ls)) (car ls))])))
Write a program to solve the following puzzle:
Dr. Z the ruler of the ancient kingdom of Joejb has her political foes locked up in individual cells in her dungeon. There are a total of 100 cells. On their Independence day as all the Joejbians were celebrating Dr. Z decided to release some of her political prisoners. But being the maverick she was she does the following: She goes to the first cell and opens it, she goes to 2nd and opens and she continues to open the 3rd, 4th ... all the way to the 100th cell. She then comes back to the 2nd cell and closes it. Shes closes the 4th and in steps of 2 she closes the 6th, 8th ... 98th and 100th cells. She then comes to the 3rd cell and this times in steps of 3 she visits each cell (3rd, 6th, 9th ...) and if the cell is open she closes it and if its closed she opens it. She repeats this process of opening closed cells and closing open cells in steps of 4, 5 ... all the up to a step of 100. In the end she decrees that all the prisoners in the cells that remain open are free to go.
Who are those lucky prisoners (ie what are their cell numbers)?
Scheme gives you the functions
putprop. They enable you to associate values with a key.
(putprop 'john 'category 'noun) (getprop 'john 'category) ==> nounWhen associating a new value with an existing key the old value is replaced. Write a function
addpropwhich doesn't replace the value associated with a key but keeps the values in a list which is added on to.
(getprop 'run 'category) ==> () (addprop 'run 'category 'verb) (getprop 'run 'category) ==> (verb) (addprop 'run 'category 'noun) (getprop 'run 'category) ==> (noun verb)
If you were to write the set operation
sets of symbols) using
membership testing routines, your program would cost on the order of m
* n where m, n are the sizes of the
individual sets (represented as lists).
Use property lists to write a more efficient version of
that is of order O(m+n) [O(2m+n) to be precise].
syntax-rules facility of Chez scheme, write a macro
begin0, which is similar to
begin. Each of
them takes a sequence of one or more expressions, and evaluates
them in order of occurrence (from left to right). However,
begin returns the value of the last expression, whereas
begin0 should return the value of the first.
(begin 1 2 3 4 5) ==> 5 (begin0 1 2 3 4 5) ==> 1
gensym in Chez provides a mechanism for
creating fresh symbols. But the notation for gensym symbols generally
isn't pleasing, so you might want to write your own symbol
generator. Write a function
newsym which behaves similar
gensym which, when invoked as a thunk returns a new
symbol each time.
(newsym) ==> g0 (newsym) ==> g1 ...But unlike
newsymso that it can also take an optional number as argument and use that as base for the counter to generate new symbols.
(newsym) ==> g2 (newsym 10) ==> g10 (newsym) ==> g11