Comp210: Principles of Computing and Programming
Fall 2004 -- Lab #3: Heterogeneous Lists   

Heterogeneous lists are those that can contain different kinds of data, e.g., symbols or numbers.

• Solution 1: Use the definition of num-or-sym.

  ; A num-or-sym is one of
  ;   - a number
  ;   - a symbol
  

  Why do we even write this -- isn't it obvious? Two reasons: First, having a concrete definition written down leads us straight to a template. Second, we want a formal name for the concept, so we can use it here:

  ; A list-of-nums-and-syms is one of
  ;   - empty
  ;   - (cons f r)
  ;     where f is a num-or-sym, and r is a list-of-nums-and-syms
  

  (Note the recursive definition!)

  The template would then follow:

       (define (func-lsn  a-losn)
          (cond
             [(empty? a-losn) ...]
             [(cons?  a-losn) ...(helper-sn (first a-losn))...
                              ...(func-losn (rest a-losn))...]))
  
  
       (define (helper-sn a-sn)
          (cond
             [(number? a-sn) ...]
             [(symbol? a-sn) ...]))
       

• Solution 2: Have one case for each kind of item.

  ; A list-of-nums-and-syms is one of
  ;   - empty
  ;   - (cons f r)
  ;     where f is a symbol, and r is a list-of-nums-and-syms
  ;   - (cons f r)
  ;     where f is a number, and r is a list-of-nums-and-syms
  

  The template then mirrors this definition, as always:

       (define (f a-losn)
          (cons
             [(empty? a-losn)          ...]
             ; Note: the next two questions assume a-losn is non-empty,
             ;       so be careful if you re-arrange these in the future.
             [(symbol? (first a-losn)) ...(first a-losn)...(f (rest a-losn))...]
             [(number? (first a-losn)) ...(first a-losn)...(f (rest a-losn))...]))
       

  Note how, for brevity, we've written the two last tests to take advantage of the sequential evaluation of conditionals. We could have used, for example, (and (cons? a-losn) (symbol? (first a-losn))) instead. The price we pay is (a) future people modifying your code need to be sure to be aware that you are implicitly depending on this order; and (b) in making this short-cut, we introduce the chance that we don't quite get the various cases correct, or in the correct order. Not bad here, but in general you might introduce bugs when making this short-cut.

Which of these two solutions is better? Both yield correct output. Does one more accurately reflect how we think about the data? (I know myself, I tend to think of it as "list of (symbol-or-number)". Which definition reflects that thinking?)

Which of them cleanly separates the processing of the list, from the processing of the individual items in the list? For instance, suppose in the future, you write more functions which keep the info represented by each symbol-or-number not inside of a list, but rather in a tree, or in pairs or in a set. The first representation lets you leave the function processing individual symbols-or-numbers unchanged, even if you later store them in containers other than lists.

Last Revised Tuesday, 24-Aug-2004 13:49:13 CDT

©2004 Stephen Wong and Dung Nguyen