Scheme Practice Problems

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.

Flat recursion

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 its car #f is returned. assoc uses 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 predicate.

        (filter odd? '(1 2 3 4 5 6 7 8 9))  ==>  (1 3 5 7 9)
Write multi-assoc in terms of filter.


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 returns #t if its a variable and #f otherwise. You can use either the * or ? prefix notation.

        (variable? '*np)        ==> #t
        (variable? "*np")       ==> #f
        (variable? '(*np jack)) ==> #f

Additional String handling

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; |(a)| represents a symbol which is flanked by a pair parenthesis.

        (symbol? '|(a)|)        ==> #t
        (symbol? '(a))          ==> #f 
        (pair? '|(a)|)          ==> #f
        (pair? '(a))            ==> #t         
Generalize explode and implode to 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.

Higher order functions

Write a function cxr that is a generalization of the car/cdr operators provided in Scheme. cxr should take a string of "a"s and "d"s representing the sequence of car and cdr operations to be performed and return a function capable of performing that sequence.

Thus (cxr "ad") is equivalent to the function cadr.

        ((cxr "ad") '(i ii iii iv v vi vii))  ==> ii
        (define sixth (cxr "addddd"))
        (sixth '(i ii iii iv v vi vii))         ==> vi

Accumulators and continuations

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.


The primitive 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-map so 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.
                '(1 2 3 4 5)
                '(10 11))                ==>  (11 13)

Using call/cc as 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))        ==> -1
There 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 member and 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/cc to 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 call/cc.


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 car, cdr, cons, cond and, 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)
      [(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)?

Property lists

Scheme gives you the functions getprop and putprop. They enable you to associate values with a key.

        (putprop 'john 'category 'noun)
        (getprop 'john 'category)       ==> noun
When associating a new value with an existing key the old value is replaced. Write a function addprop which 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)

Property lists

If you were to write the set operation intersection (on 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 intersection that is of order O(m+n) [O(2m+n) to be precise].


Using the 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

Local state

The function 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 to gensym which, when invoked as a thunk returns a new symbol each time.

        (newsym)        ==> g0
        (newsym)        ==> g1
But unlike gensym write newsym so 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