SCHEME  Sample Questions     

    These are not guaranteed to collectively represent an exam,
    but they form a reasonable approximation. (Question 2 is a
    bit subtle; the case of the empty list being one of the
    elements in a non-empty list has to be handled properly.)




  1.   Assume the following SCHEME expressions are evaluated:

       (define A 3)                 
       (define B 'A)
       (define C '(A B))
       (define D (list B A))
       (define A2 (lambda (L) (cddr L)))


Now assume that each of the expressions below is entered into SCHEME
and evaluated after the expressions on the left are. In each case,
show what SCHEME's response would be. (2 pts. each)

A        _______________________________________

'B        _______________________________________

(A2  '(A  B))        _______________________________________

(A2  (list  A  B))        _______________________________________

(cond (()  C) (#t  17  B))        ______________________________________

(eq?  C  (cons  'A  3))        _______________________________________

(equal?  C  '(A  B))        _______________________________________

(eq?  (cons A  B)  (cons  3  'A))      __________________________________

(A2  (list B  'B  B))        _______________________________________

(pair?  B)        _______________________________________

(pair?  'B)        _______________________________________

(null?  (cdr  '(A  .  B)))        _______________________________________

(null?  (cadr  (list  1  ( )  B) ))     _________________________________


  2.   Compose a SCHEME function listels that when given an  arbitrary
       list  structure,  returns  as  its value the number of atomic
       list elements in the entire list structure (not the number of
       leaves in the binary tree representation). You may  assume that
       listels  will  be  called  only  on pure list structure.  For
       example,  listels  will  not  be  called  initially  on   'a,
       '(a . b), '(a (d . f) c),  etc.


       (listels  '(a b c))  =  (listels  '(a (b) c))  =  3

       (listels  ())  =  0            (listels  '(()))  =  1

       (listels  '( (a  b)  c  (()  d  a  (b  (g))) ) )  =  8


  3.  Compose a SCHEME function nthel that when given a positive
       integer n and a list, returns the n-th element of that list. If
       the list has fewer than n elements, the value should be
       undefined.

       (nthel 3 '(a b c))  =  (nthel 3 '(a (b x (y z)) c d))  =  c

       (nthel 1 '( (a  b)  c  (nil d a (b (g))) ) ) = (a b)

       (nthel 7 '(1 2 3 4 5 6)) = No value


  4.   Write a function disagree that takes two LISTS  as  arguments
       and returns an integer >= 1 such that:

       (disagree  L1  L2)  =  N  means that the first N-1 elements of  L1
        and L2 are equal pairwise, but their N-th elements are not.

       (disagree  '(a b c)  '(a c d))  =  2
       (disagree  '(a b c d)  '(a b))  =  3
       (disagree  ()  ())  =  1   (this convention makes life easier)
       (disagree  '(a b)  '(a b))  =  3
       (disagree  '((a b)  (a b))  '((a b)  (b a)))  =  2
       (disagree  '(a b)  '(b a))  =  1




\\\\\\\\\\\\\\\\\\\\\\\\\\\\\   ANSWERS   \\\\\\\\\\\\\\\\\\\\\\\\\\\\\


1.

       A                                         3
       'B                                        B
       (A  '(A  B))                              ()
       (A  (list  A  B))                         ()
       (cond (()  C) (t  17  B))                 A
       (eq?  C  (cons  'A  3))                   ()
       (equal?  C  '(A  B))                      #t
       (eq?  (cons A  B)  (cons  3  'A))         ()
       (A2  (list B  'B  B))                     (A)
       (pair?  B)                                ()
       (pair?  'B)                               ()
       (null?  (cdr  '(A  .  B)))                NIL
       (null?  (cadr  (list  1  ( )  B) ))       #t



2.
       (define  listels  (lambda  (L)
          (cond  ((null?  L)  0)
                 ((not (pair? L))  1)
                 ((null?  (car L))  (+  1   (listels  (cdr L))))
                 (#t  (+  (listels  (car L)) (listels  (cdr L)))) ) ))


3. 

; Notice the way the testing is organized here using the cond
; function so that nthel is undefined when the list is too short.

      (define  nthel  (lambda (n  L)
                 (cond  ((> n 1)
                         (cond ((not (null? (cdr L)))
                                (nthel (- n 1) (cdr L)) )) )
                        ((not (null? L))  (car L)) ) ))



4.

  (define  disagree  (lambda (L1  L2)
    (cond  ((or  (null?  L1)  (null?  L2))  1)
           ((equal?  (car L1)  (car L2))
            (1+  (disagree  (cdr L1)  (cdr L2))) )
           (#t  1) ) ))