where pred? is a predicate on atoms. Is the let-binding desirable in this example?

Would we be better off with:

 (define (subst*2 new lst)
   (cond
     [(null? lst) null]
     [(atom? (car lst))
      (if (pred? (car lst))
          (cons new (subst*2 new (cdr lst)))
          (cons (car lst) (subst*2 new (cdr lst))))]
     [else
       (cons (subst*2 new (car lst))
             (subst*2 new (cdr lst)))]))

Is there any efficiency difference between these two versions?

Example: Flatten a list

 ; removes all but outer parentheses from list
 (define (flatten lst)
   (cond
     [(null? lst) null]
     [(atom? (car lst))
        (cons (car lst)
              (flatten (cdr lst)))]
     [else
      (append (flatten (car lst))
              (flatten (cdr lst)))]))

Exercise: write a two-argument version of append (Scheme's append takes an arbitrary number of arguments).

Embedding data structures in lists

A list of atoms can be viewed a tree, all of whose branches go to the right. Lists containing nested lists are trees with more elaborate branching structure. By specifying list structures, we can use lists to embed tree-like data structures. Now, the modern Scheme approach to encode such trees would be to use Scheme structures, which are records with named fields. It's still a useful exercise to think about embedding trees into lists. For one thing, structures currently differ among Scheme implementations.

Definition: A ternary tree of numbers is either

• a number, or

• a four-element list consisting of a number and three ternary trees of numbers

From this definition, we can write a predicate tton? that returns true if its input is a ternary tree of numbers, and false otherwise.

 (define (tton? x)
   (cond
    [(number? x) #t]
    [(pair? x)
      (cond 
        [(null? (cdr x)) #f]   ; 1-element list
        [(null? (cddr x)) #f]  ; 2-element list
        [(null? (cdddr x)) #f] ; 3-element list
        [(null? (cddddr x))    ; 4-element list
         (and (number? (car x))
              (tton? (cadr x))
              (tton? (caddr x))
              (tton? (cadddr x)))]
        [else #f])]            ; > 4 elements
    [else #f]))               

For the second clause in the cond, we could have asked

  (and (pair? x) (= (length x) 4))

and skipped the checks for null?. That would work, so why didn't we take that approach?

Those null? checks are used to determine the input list's length. We could instead use a two-argument predicate, has-length?, which takes a list and a number, and returns #t if the list has a length equal to the number, and #f otherwise:

  (define (has-length? lst n)
    (cond 
      [(null? lst) (zero? n)]
      [(<= n 0) #f] ; optional, really
      [else (has-length? (cdr lst) (sub1 n))]))

Why would we prefer this predicate to length? Claim: this procedure will compute the expected result without the middle clause of the cond. So why is it there? What happens if the input list has one billion elements, and n is one million?