Guided Practice 8.1

1. Write a data definition for SortedList. Hint: You will need an invariant.

   There are probably many ways of doing this. Here's one solution:

   A SortedList is one of
   -- empty
   -- (cons Number SortedList)
      WHERE: the Number is less than or equal to any of the elements in
             the SortedList
   

   If you have a different solution, we can discuss it in class or on Piazza.

2. Write two DIFFERENT function definitions for even-elements and odd-elements. Assume the elements of the list are numbered starting at 1.

   EXAMPLES:
   (odd-elements (list 10 20 30 40)) = (list 10 30)
   (even-elements (list 10 20 30 40)) = (list 20 40)
   (odd-elements (list 10)) = (list 10)
   (even-elements (list 10)) = empty
   

   Here are my solutions:

   ;; Solution 1:
   
   ;; odd-elements : ListOfNumber -> ListOfNumber
   (define (odd-elements lst)
     (cond
       [(empty? lst) empty]
       [(empty? (rest lst)) (list (first lst))]
       [else (cons
               (first lst)
               (odd-elements (rest (rest lst))))]))
   
   ;; even-elements : ListOfNumber -> ListOfNumber
   (define (even-elements lst)
     (cond
       [(empty? lst) empty]
       [(empty? (rest lst)) empty]
       [else (cons
               (first (rest lst))
               (even-elements (rest (rest lst))))]))
   
   ;; These functions do not follow the template for ListOfNumber.  They
   ;; both recur on (rest (rest lst)), not on (rest lst).  In addition,
   ;; they both have a special case for lists of length 1.
   
   ;; Solution 1A:
   
   ;; We could get rid of the special case by moving it into the else
   ;; branch, like this: 
   
   (define (odd-elements lst)
     (cond
       [(empty? lst) empty]
       [else (if (empty? (rest lst)) 
                 (list (first lst))
                 (cons
                  (first lst)
                  (odd-elements (rest (rest lst)))))]))
   
   (define (even-elements lst)
     (cond
       [(empty? lst) empty]
       [else (if (empty? (rest lst)) 
                 empty
                 (cons
                  (first (rest lst))
                  (even-elements (rest (rest lst)))))]))
   
   ;; but that doesn't get around the non-structural recursion on
   ;; rest-of-rest.
   
   ;; I don't think this is really different from solution 1.
   
   ;; Solution 2:
   
   ;; Here's a very different solution.  Here we make odd-elements and
   ;; even-elements mutually recursive:
   
   (define (odd-elements lst)
     (cond
       [(empty? lst) empty]
       [else (cons
               (first lst)
               (even-elements (rest lst)))]))
   
   (define (even-elements lst)
     (cond
       [(empty? lst) empty]
       [else (odd-elements (rest lst))]))