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:

   ;; odd-elements : ListOfNumber -> ListOfNumber
   ;; Strategy: Recur on (rest (rest lst))
   (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
   ;; Strategy: Recur on (rest (rest lst))
   (define (even-elements lst)
     (cond
       [(empty? lst) empty]
       [(empty? (rest lst)) empty]
       [else (cons
               (first (rest lst))
               (even-elements (rest (rest lst))))]))
   
   ;; Solution 2:
   
   ;; Here's a very different solution.  Here we make odd-elements and
   ;; even-elements mutually recursive.  This actually fits into the
   ;; destructor template for ListOfX. Here we are recurring on (rest
   ;; lst), so this could fairly be called structural recursion.
   
   ;; strategy: Use template for ListOfX on lst
   (define (odd-elements lst)
     (cond
       [(empty? lst) empty]
       [else (cons
               (first lst)
               (even-elements (rest lst)))]))
   
   ;; strategy: Use template for ListOfX on lst
   (define (even-elements lst)
     (cond
       [(empty? lst) empty]
       [else (odd-elements (rest lst))]))