- (15 points)
Write a procedure
insert-at
that inserts a
given element into a list in a specified position. Assume that the
positions are numbered from 0, and that the position specified
is always 0 or positive. If the position is greater than
the length of the list the procedure should return the list itself.
It should work like this:
STk> (insert-at 'k 3 '(b c m n))
(b c m k n)
STk> (insert-at 'a 0 '(b c d e))
(a b c d e)
STk> (insert-at 'a 7 '(b c d e))
(b c d e)
- (15 points)
Write a procedure
(expand lst)
that takes as an argument a list.
The elements of the list are either symbols or lists of two elements,
a strictly positive integer (i.e. greater than 0) and a symbol.
The integer is a repeat count, meaning that the symbol following it
should be repeated that many times.
The procedure should return a list
where the repeated symbols are expanded, i.e. each sublist
(< number > < symbol >) is replaced by a list with the
symbol repeated < number > times.
You cannot use any global variable, but you are free to use as many
auxiliary procedures as you like.
It should work like this:
STk> (expand '(oh (2 ah)))
(oh (ah ah))
STk> (expand '(school is (1 very) hard))
(school is (very) hard)
- (10 points)
Write a procedure
(replace old new lst)
to replace
every occurrence
of the element old in the list lst with new.
If the element does not appear in the list, the list should be returned
unchanged. It should work like this:
STk> (replace 3 -3 (list 3 4 1 2 3))
(-3 4 1 2 -3)
STk> (replace 1 11 (list 3 2 10))
(3 2 10)
STk> (replace 1 '(2 3) '(3 1 4 2))
(3 (2 3) 4 2)
- (10 points)
Write a procedure
running-sum
that given a list produces a
new list that contains, as each element in the new list, the sum of
all corresponding elements up to that point in the original list.
It should work like this:
STk> (running-sum (list 1 3 9 2))
(1 4 13 15)
;where 4 = 1+3, 13 = 1+3+9, 15=1+3+9+2
STk> (running-sum (list 2 2 2 2 2))
(2 4 6 8 10)
STk> (running-sum (list 2))
(2)
- (10 points)
Write a predicate
(find pred tree)
that returns
a list of the elements of the tree that satisfy the predicate.
It should work like this:
STk>(find odd? '(3 (2 (1 3) 9)))
(3 1 3 9)
STk>(find even? '((3 11) 5))
()
- (10 points)
Write a procedure
inc1-even
that takes as an argument a
tree whose elements are numbers and increments by one all the numbers
that are even.
It should work like this:
STk> (inc1-even '(1 (2 (3 4) 8 10) 9 (11)))
(1 (3 (3 5) 9 11) 9 (11)))
STk> (inc1-even '(1 (5 (3))))
(1 (5 (3)))
- (10 points)
Write a procedure (remove-el el set) to remove an element
from a set represented by an ordered list. If the element does not
exist in the set, the procedure should return the same set.
Write the procedure to take advantage of the ordering of the elements
of the set to speedup the computation. It should work like this:
STk> (remove-el 3 (list 2 3 7))
(2 7)
STk> (remove-el 5 (list 2 3 7))
(2 3 7)
- (10 points)
Write a predicate
(set-diff set1 set2)
to compute
the difference of
two sets, which is the set containing each element that appears in
set1 but not in set2.
Assume the sets are represented by ordered lists.
To get full credit you have to write the predicate to take advantage
of the ordering of the elements of the sets.
It should work like this:
STk> (set-diff '(2 5 7 9 25) '(2 7 9) )
(5 25)
STk> (set-diff '(2 5 7 9 25) '(3 8) )
(2 5 7 9 25)
STk> (set-diff '(2 3) '(2 3) )
()
- (10 points)
You are given the following procedures from the textbook:
(define (attach-tag type-tag contents)
(cons type-tag contents))
(define (type-tag datum)
(if (pair? datum)
(car datum)
(error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
(if (pair? datum)
(cdr datum)
(error "Bad tagged datum -- CONTENTS" datum)))
and the following definition
(define mytree '(a (b (c)) d))
- Show the procedure call to attach the tag
tree
to
mytree
by completing the following:
(define tagged-tree ??)
- Show the values of the following expressions:
(contents tagged-tree)
(type-tag tagged-tree)
- Show the internal representation of
tagged-tree
.
Draw the cons box representation.