comp210 Exam#1 Solutions -- Problem 2

1998 Spring

• 0, or
• (add1 m), where m is a <natNum>.

1. Write the template for a function which handles two arguments: a <natNum> and a <list-of-symbol>. Make sure all cases are covered.

   The best solution, with an arbitrary ordering of cond clauses, is

   (define template
      (lambda (n los)
         (cond [(and (zero? n) (null? los)) ...]
               [(and (zero? n) (cons? los)) ...(first los)...(rest los)...]
               [(and (positive? n) (null? los))  ...(sub1 n)...]
               [(and (positive? n) (cons? los))
                ...(first los)...
                ...(template (sub1 n) los)...
                ...(template (sub1 n) (rest los))...
                ...(template n (rest los))...])))
   

   It was acceptable to simply have one of these instances of natural recursion.

2. Write the function nth-rest, which takes a <natNum> n and a <list-of-symbol> los, and returns los without its first n items, or the symbol 'list-too-short if los has fewer than n items.

     (nth-rest 2 (list 'four 'scores 'and 'twenty))
   = (list 'and 'twenty)
   

   You may simplify and combine cases if you like, but be careful! Indicate whether or not you can rearrange your cond's question/answer pairs and still produce the correct answer.

   The verbose solution, derived from the template, is

   (define nth-rest
      (lambda (n los)
         (cond [(and (zero? n) (null? los)) null]
               [(and (zero? n) (cons? los)) los]
               [(and (positive? n) (null? los))  'list-too-short]
               [(and (positive? n) (cons? los))  (nth-rest (sub1 n) (rest los))])))
   

   In this solution, the cond clauses may be reordered arbitrarily.

   The most simplified solution is

   (define nth-rest
      (lambda (n los)
         (cond [(zero? n)   los]
               [(null? los) 'list-too-short]
               [else        (nth-rest (sub1 n) (rest los))])))
   

   In this solution, the cond clauses may not be reordered.