Lecture notes:  recursion on lists

Like many other data structures, lists in Scheme have a recursive
nature that shows up in the definition of what list is.  For instance,
one way to describe a list is to say

a list is either
 - the empty list ()
 - or a cons, which has	
    - a car, which is anything, and
    - a cdr, which is a list

Note that list appears in the definition of list.

When we can describe a data structure recursively, it is often the case that
we can use the structure of the description to guide us in writing
recursive functions that operate on this data structure.  The
definition above suggests a function with the following structure:


(define (fn x)
  (if (null? x) A
      (B (C (car x))
         (fn (cdr x)))))

where A is some value and B and C are some functions.  So, length is
(define (length x)
  (if (null? x) 0
      (+ 1
         (length (cdr x)))))

Here A is 0, B is +, C is a function that always returns 1.

Reverse is
(define (reverse x)
  (if (null? x) '()
      (append (reverse (cdr x))
              (list (car x)))))
A is (), B is (lambda (l1 l2)(append l2 l1)), C is list.


Sometimes we are really thinking of a list as a binary tree.  (Remember
from 112 that a linked list can be seen as a binary tree and vice versa.)
In scheme terms, we are thinking of an S-expr:

An S-expr is
  - an atom (a symbol or a number), or
  - (), or
  - a cons, which has a car, and a cdr, both of which are S-exprs

This gives the code structure
(define (fn x)
  (cond ((null? x) A)
        ((not (list? x)) (B x))
        (else (C (fn (car x))
                 (fn (cdr x))))))

E.g., 
(define (countatoms x)
  (cond ((null? x) 0)
        ((not (list? x)) 1) 
        (else (+ (countatoms (car x))
                 (countatoms (cdr x))))))

A is 0, B is a function that always returns 1, and C is +

Finally, sometimes we are thinking of an S-expr as a list, whose elements
are atoms or lists, i.e.
An S-expr is
 - an atom or
 - a list, which is
    - () or
    - a cons, which has a car that is a S-expr and a cdr that is a list

(Note that since the cdr cannot be an atom, it is a list rather than a
S-expr.)

This gives a code structure with two functions, one to handle S-exprs
in general and one to handle lists

(define (fn-sexpr x)
  (if ((not (list? x) (A x)
      (fn-list x)))

(define (fn-list x)
  (if (null? x) A
      (B (fn-sexpr(car x))
         (fn-list (cdr x)))))
         

E.g., count-rp counts the right parens in the printed representation of
a S-expr:

(define (count-rp x)
  (if (not (list? x)) 0    ; an atom has no parens
      (count-rp-list x)))  ; not an atom, must be a list

;;; count right parens in list, including paren that ends the list
(define (count-rp-list x)
  (if (null? x) 1                    ; () has one right paren
      (+ (count-rp (car x))
         (count-rp-list (cdr x)))))


count-lp counts left-parens in the printed representation of a S-expr

(define (count-lp x)
  (if (not (list? x)) 0   ; atom has no parens
      (+ 1 (count-lp-list x))))  ; left paren at start plus left parens
                                 ; in elements

;;; left parens in elements of a list
(define (count-lp-list x) 
  (if (null? x) 0     ; no elements-> no parens is elements
      (+ (count-lp (car x))
         (count-lp-list (cdr x)))))