Processing Two Lists Simultaneously: Case 3

Here is a third problem statement, given as in the form of a function contract, purpose statement, and header:

;; list-pick : list-of-symbols N[>= 1] -> symbol
;; to determine the nth symbol from alos, counting from 1; 
;; signals an error if there is no nth item 
(define (list-pick alos n) ...) 

The data definitions: A natural number [>= 1] (N[>= 1]) is either 1 or (add1 n) if n is a N[>= 1]. A list-of-symbols is either the empty list, empty, or (cons s lof) where s is a symbol and lof is a list of symbols. Figure: Data definitions for list-pick

Because the problem is non-standard, we should ensure that our examples cover all important cases. We usually accomplish this goal by picking one item per clause in the definition and choosing elements from basic forms of data on a random basis. In this example, this procedure implies that we pick at least two elements from list-of-symbols and two from N[>= 1]. Let's choose empty and (cons 'a empty) for the former, and 1 and 3 for the latter. But two choices per argument means four examples total; after all, there is no immediately obvious connection between the two arguments and no restriction in the contract:

(list-pick empty 1) 
;; expected behavior:  
(error 'list-pick ``...'') 

(list-pick (cons 'a empty) 1)
;; expected value:  
'a 

(list-pick empty 3) 
;; expected behavior:  
(error 'list-pick ``...'') 

(list-pick (cons 'a empty) 3)
;; expected value:  
false 

The discussion on examples indicates that there are indeed four possible, independent cases that we must consider for the design of the function. We can discover the four cases by arranging the necessary conditions in a table format:

The horizontal dimension of the table lists those questions that list-pick must ask about the list argument; the vertical dimension lists the questions about the natural number. Furthermore, the partitioning of the table yields four squares. Each square represents the case when both the condition on the horizontal and the one on the vertical are true. We can express this fact with and-expressions in the squares:

	(empty? alos)	(cons? alos)
(= n 1)	(and (= n 1) (empty? alos))	(and (= n 1) (cons? alos))
(> n 1)	(and (> n 1) (empty? alos))	(and (> n 1) (cons? alos))

It is straightforward to check that for any given pair of arguments exactly one of the four composite claims must evaluate to true.

Using our cases analysis, we can now design the first part of the template, the conditional expression:

(define (list-pick alos n)
  (cond 
    [(and (= n 1) (empty? alos)) ...] 
    [(and (> n 1) (empty? alos)) ...] 
    [(and (= n 1) (cons? alos)) ...] 
    [(and (> n 1) (cons? alos)) ...])) 

(define (list-pick n alos)
  (cond 
    [(and (= n 1) (empty? alos)) 
     ...] 
    [(and (> n 1) (empty? alos)) 
     ... (sub1 n) ...] 
    [(and (= n 1) (cons? alos)) 
     ... (first alos) ... (rest alos)...] 
    [(and (> n 1) (cons? alos)) 
     ... (sub1 n) ... (first alos) ... (rest alos) ...])) 

The final step of the template construction demands that we annotate the template with recursions where the results of selector expressions belong to the same class as the inputs. In the template for list-pick, this makes sense only in the last cond-clause, which contains both a selector expression for N[>= 1] and one for list-of-symbols. All other clauses contain at most one relevant selector expression. It is, however, unclear how to form the natural recursions. If we disregard the purpose of the function, and the template construction step asks us to do just that, there are three possible recursions:

1. (list-pick (rest alos) (sub1 n))
2. (list-pick alos (sub1 n))
3. (list-pick (rest alos) n)

;; list-pick : list-of-symbols N[>= 1] -> symbol ;; to determine the nth symbol from alos, counting from 1; ;; signals an error if there is no nth item (define (list-pick n alos) (cond [(and (= n 1) (empty? alos)) (error 'list-pick ``list too short'')] [(and (> n 1) (empty? alos)) (error 'list-pick ``list too short'')] [(and (= n 1) (cons? alos)) (first alos)] [(and (> n 1) (cons? alos)) (list-pick (rest alos) (sub1 n))])) Figure: The complete definition of list-pick

Following the design recipe, let us analyze each cond-clause in the template and decide what a proper answer is:

1. If (and (= n 1) (empty? alos)) holds, list-pick was asked to pick the first item from an empty list, which is impossible. The answer must be an application of error.
2. If (and (> n 1) (empty? alos)) holds, list-pick was again asked to pick an item from an empty list. The answer is also an error.
3. If (and (= n 1) (cons? alos)) holds, list-pick is supposed to produce the first item from some list. The selector expression (first alos) reminds us how to get this item. It is the answer.
4. For the final clause, if (and (> n 1) (cons? alos)) holds, we must analyze what the selector expressions compute:
   1. (first alos) selects the first item from the list of symbols;
   2. (rest alos) is the rest of the list; and
   3. (sub1 n) is one less that the original given list index.
   Let us consider an example to illustrate the meaning of these expressions. Suppose list-pick is applied to (cons 'a (cons 'b empty)) and 2:

      (list-pick (cons 'a (cons 'b empty)) 2)
   

   The answer must be 'b, (first alos) is 'a, and (sub1 n) is 1. Here is what the three natural recursions would compute with these values:

   1. (list-pick (cons 'b empty) 1) produces 'b, the desired answer;
   2. (list-pick (cons 'a (cons 'b empty)) 1) evaluates to 'a, which is a symbol, but the the wrong answer for the original problem; and
   3. (list-pick (cons 'b empty) 2) signals an error because the index is larger than the length of the list.
   This suggests that we use (list-pick (rest alos) (sub1 n)) as the answer in the last cond-clause. But, example-based reasoning is often treacherous, so we should try to understand why the expression works in general.

   Recall that, according to the purpose statement,

   (list-pick (rest alos) (sub1 n))
   

   picks the (n-1)st item from (rest alos). In other words, for the second application, we have decreased the index by 1, shortened the list by one item, and now look for an item. Clearly, the second application always produces the same answer as the first one, assuming alos and n are ``compound'' values. Hence our choice for the last clause is truly justified.

Develop list-pick0, which picks items from a list like list-pick0 but starts counting at 0.

Examples:

(symbol=? (list-pick0 (list 'a 'b 'c 'd) 3)
         'd) 

(list-pick0 (list 'a 'b 'c 'd) 4)
;; expected behavior: 
(error 'list-pick0 ``the list is too short'')