'(a (((b))) (((((((c))))))) d)

The time required to calculate the length of this list is the same as for any 4-element list, because the nesting structure is irrelevant to that calculation.

With so-called flat recursion, procedures have the form

 (define (proc lst)
   (if (null? lst)
      ... do something with the empty list ...
      ; otherwise
      ... somehow combine (car lst) with (proc (cdr lst)) ...

What's explicitly missing from this formulation is a recursive call on the car of the input -- even though it may itself be a list.

Example: Find an atom anywhere in a list

 ; assumes lists and atoms only data in Scheme
 ; that's not true, but we'll pretend
 (define (atom? x)
   (not (or (null? x)
            (pair? x))))

 ; returns #t if atom `atm' anywhere
 ;  in possibly-nested list, #f otherwise
 (define (member* atm lst)
   (cond
     [(null? lst) #f]
     [(atom? (car lst))
      (or (eq? atm (car lst))
          (member* atm (cdr lst)))]
     [else ; car must be list
      (or (member* atm (car lst))
          (member* atm (cdr lst)))]))

Example:

  (member* 'a '(b a c)) => #t
  (member* 'a '((b) (((a c)))) => #t
  (member* 'a '((b) (((d c)))) => #f

Scheme does have a primitive named list?, which we could use in place of atom?. But it's generally a bad idea to use list? -- why?

Note that in member*, there are several recursive calls. We need them both -- why? How much of the list does this procedure traverse? Does it ever traverse the entire list? An ``extensionally-equivalent'' procedure is:

 (define (member*2 atm lst)
   (if (null? lst) 
     #f
     (let ([cdr-result (member*2 atm (cdr lst))])
       (if (atom? (car lst))
         (or (eq? atm (car lst))
             cdr-result)
         (or (member*2 atm (car lst))
             cdr-result)))))

The let form creates a local binding that is visible in the let body. A let is useful for performing a computation whose result may be used more than once. Which version should we prefer?

Example: Substitute for an atom anywhere in a list

 ; substitutes `new' for atom satisfying `pred?' anywhere in 
 ;  possibly-nested input list
 ; nesting structure of input list is preserved in output
 (define (subst* new lst)
   (if (null? lst) 
       null
       (let ([cdr-result (subst* new (cdr lst))])
         (if (atom? (car lst))
           (if (pred? (car lst))
             (cons new cdr-result)
             (cons (car lst) cdr-result))
           (cons (subst* new (car lst))
                 cdr-result)))))