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 sorted list of reals is represented as a SortedList, which is one of
   -- empty
   -- (cons r sl)
      WHERE: the Number is less than or equal to any of the elements in
             the SortedList
   INTERPRETATION:
   r  : Real        is the first element of the list
   sl : SortedList  is the rest of the list
   
   CONSTRUCTOR TEMPLATES:
   (empty)
   (cons Real SortedList)
   
   OBSERVER TEMPLATE:
   ;; sl-fn : SortedList -> ??
   (define (sl-fn lst)
     (cond
       [(empty? lst) ...]
       [else (f (first lst)
                (sl-fn (rest lst)))]))
   WHERE:
   f may rely on the invariant that its first argument is less than any of
   the elements of its second argument.
   

   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 : RealList -> RealList
   ;; 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 : RealList -> RealList
   ;; 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
   ;; observer template for RealList. Here we are recurring on (rest
   ;; lst), so this could fairly be called structural recursion.
   
   ;; strategy: Use template for RealList on lst
   (define (odd-elements lst)
     (cond
       [(empty? lst) empty]
       [else (cons
               (first lst)
               (even-elements (rest lst)))]))
   
   ;; strategy: Use template for RealList on lst
   (define (even-elements lst)
     (cond
       [(empty? lst) empty]
       [else (odd-elements (rest lst))]))
   

---

Last modified: Fri Oct 13 11:07:21 Eastern Daylight Time 2017