Fall '98 C311 Quiz

Write your name at the top of the page and finish defining the following Scheme procedures. You have 45 minutes. Follow the cardinal rules of indentation, and use any extra time to check your work.

1. first-symbol takes a list and returns the first top-level symbol in the list, or #f if there is no symbol in the list.

   ;; (first-symbol '(1 #t '(a) b c 4)) ==> b
   ;; (first-symbol '((a))) ==> #f
   
   (define first-symbol
     (lambda (ls)
   
   
   
   
   
   
   
     ))
   

2. last-number takes a list and returns the last top-level number in the list, or #f if there is no symbol in the list.

   ;; (last-number '(1 c 4 (5))) ==> 4
   
   (define last-number
     (lambda (ls)
   
   
   
   
   
   
   
     ))
   

3. union takes two lists of symbols without duplicates, set1 and set2, and returns a new list containing all the symbols in set1 or set2, without duplicates.

   ;; (union '(a b c d e) '(d h b g)) ==> (a b c d e h g)
   
   (define union
     (lambda (set1 set2)
   
   
   
   
   
   
   
   
   
   
   
   
     ))
   

4. count-symbols* takes a nested list and returns the total number of symbols in the list at all depths.

   ;; (count-symbols* '((a b) 4 c () ((d)))) ==> 4
   
   (define count-symbols*
     (lambda (nls)
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
     ))
   

5. ribassoc takes a symbol, s, a list of symbols, los, a vector, v, and a fail-value, and returns the value in v that is associated with s, or fail-value if there is not associated value. If the first occurence of s in los has index n, the value associated with s is the nth value in v. There is not associated vale for s if s is not a member of los. You may assume that los and v are the same length.

   ;; (ribassoc 'b (a b c) '#(1 2 3) 'fail) ==> 2
   ;; (ribassoc 'c '(a b foo) '#(3 squiggle bar) 'fail) ==> fail
   
   (define ribassoc
     (lambda (s los v fail-value)
   
   
   
   
   
   
   
   
   
   
   
   
   
   
     ))
   

6. flatten takes a nested list, slst, and returns a list of the symbols contained in slst in the order in which they occur when slst is printed. Intuitively, flatten removes all the inner parentheses from its arugment.

   ;; (flatten '((a b) c (((d)) e))) ==> (a b c d e)
   ;; (flatten '(a b (() (c)))) ==> (a b c)
   
   (define flatten
     (lambda (slst)
   
   
   
   
   
   
   
   
   
   
   
   
   
   
     ))

7. shape takes a nested list structure and return a list structure that prints in such a way that the parenthesis structure is maintained, but everything else is removed.

   ;; (shape '(a ((b)) (3)) ==> ((()) ())
   ;; (shape '((a) () 4 ((())))) ==> (() () ((())))
   
   (define shape
     (lambda (nls)
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
     ))