# Problem Set Four, CS 257

Due at 9am on Fri Feb 26, 1999

## S-Expression Finger Exercises

The below definitions should use simple recursion. Naturally you may
define auxiliary functions. Your solution to one of the below
problems may use something defined in another one, or even use another
one as a subroutine. (5 points each)
- Define
`iota0` which takes a non-negative integer
*n* and returns a list of numbers from *n-1* to 0. Eg
`(iota0 5)` yields `(4 3 2 1 0)`.
- Define
`noah` which takes two lists of the same length
and returns a list of corresponding pairs. Eg
`(noah '(aye bee sea) '(one two three))`
returns `((aye one) (bee two) (sea three))`
- Define
`fill-list` which takes two arguments, the first
being a non-negative integer *n*, and returns a list of length
*n* each of whose elements are the second argument. Eg
`(fill-list 3 'z)` yields `(z z z)`.
- Define
`nthcdr` which takes a list and a non-negative
integer and returns the ``n^{th} cdr'' of the given list. Eg
`(nthcdr '(a b c d e) 3)` yields `(d e)`.
- Define
`flatten` which takes an sexpr as its sole
argument, and returns a flat list of all the (possibly deeply nested)
atoms in that argument. Eg `(flatten '(a (b c) d (e (f) g) ()
h))` yields `(a b c d e f g h)`.
- Define
`nth` which takes a list and non-negative integer
*n* and returns the *n*^{th} element of the given list -
counting from zero of course.
Eg `(nth '(a b c d e f) 2)` yields `c`.
- Define
`bleepout` which takes an sexpr and a list of
naughty symbols, and replaces any naughty word in the association list
with the symbol `***`. Eg
(bleepout '(strongly (typed c) c++ cobol hacking
(perl lover) microsoft drone)
'(perl cobol c++ microsoft))

yields `(strongly (typed c) *** *** hacking (*** lover) *** drone)`
- Define
`junkmail` which takes an sexpr and a list, and
returns an sexpr similar to the one it was passed except non-negative
integers have been replaced by corresponding items from the list. Eg
(junkmail '((dear 0)
(your 3 4 has died while under our care)
(you and your spouse 2 1 have our condolences)
(as do all the 1 children)
(most sincerely yours))
'(brian crawford lisa cat fluffy))

yields
((dear brian)
(your cat fluffy has died while under our care)
(you and your spouse lisa crawford have our condolences)
(as do all the crawford children)
(most sincerely yours))

#### Extra Credit

Define `s-morph`, which takes two s-expressions as arguments,
and returns an sexpr that has the ``shape'' of the second argument, but
the ``contents'' of the first. (5 points.) Eg
(s-morph '((((1 2) 3) 4) 5 (((6 7 8))))
'(a (b c) d (e (f) g) () h))

returns
`(1 (2 3) 4 (5 (6) 7) () 8)`
#### Submission

Turn in this problem set by running `~cslab/bin/cs257-handin file.scm`.

Barak Pearlmutter <bap@cs.unm.edu>