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)

  1. 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).

  2. 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))

  3. 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).

  4. Define nthcdr which takes a list and a non-negative integer and returns the ``nth cdr'' of the given list. Eg (nthcdr '(a b c d e) 3) yields (d e).

  5. 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).

  6. Define nth which takes a list and non-negative integer n and returns the nth element of the given list - counting from zero of course. Eg (nth '(a b c d e f) 2) yields c.

  7. 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)

  8. 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>