Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution:
A Proper List Predicate

Here is a solution programmed with or and and:

 
(define (proper-list? x)
  (or (null? x)
      (and (pair? x) (proper-list? (cdr x)))))

It is, of course, also possible to write the function using if.

 
(define (proper-list-1? x)
  (if (null? x)
      #t
      (if (pair? x)
          (proper-list-1? (cdr x))
          #f)))

This version is more verbose, and less elegant. Both versions are memory efficient (tail recursive). Notice, however, that it is rather costly to use the proper list predicate, because it will have to iterate to the end of the cdr chain to find out if the list is proper or not. There are no possible shortcuts as long as we rely on (single) linked lists.