Day dreams to grow great.

Write safe Scheme procedure that handles only proper list January 3, 2010

Filed under: Uncategorized — day @ 17:28

C does not have a string type, thus a string is actually constructed via an array of characters, with a special NUL character marking its end. Similarly, Scheme does not have a list type, a list is actually consed recursively from pairs, with a special constant nil marking its end. The lack of a true list type results in the distinction of “proper list” (consed pairs ended with a nil) and “improper list” (consed pairs not ended with a nil), for example, (0 1 2) is a pretty printed form for (0 . (1 . (2 . nil))), and more primitively (cons 0 (cons 1 (cons 2 nil))), while (0 1 . 2) for (0 . (1 . 2)), in turn (cons 0 (cons 1 2)). Although improper list is rarely used in Scheme (as a dialect of Lisp, it of course does a lot of (proper) list processing), we can not presume that one will call a procedure intended to handle a proper list with indeed a proper one. So when writing a procedure that expects to handle a proper list, we need to take care of the extreme case.

SRFI-1 provides a pair of procedures proper-list? and improper-list? for testing whether a list is proper or not respectively. Thus when we write a procedure to handle proper list, we can first check to see if the passed in argument is a proper list before we actually deals with it. For example, the standard length procedure could be defined as follows:

   (define (length l)
     (cond ((improper-list? l) (print "Error: passed in an improper list"))
           ((null? l) 0)
           (else (+ 1 (length (cdr l))))))

It’s easy to see that both proper-list? and improper-list? need to traverse the list before they can tell whether the list is proper or not. To avoid this unnecessary traversal, we can embed the test inline as shown below:

   (define (length l)
     (cond ((pair? l) (+ 1 (length (cdr l))))
           ((null? l) 0)
           (else (print "Error: passed in an improper list"))))

This version of length seems better than the first one, however, it may not generally be true. For a general procedure on list, the late coming info about the proper/improper attribute of the list (we don’t till the end) may make us do much useless work on every element of the list except the last.



Get every new post delivered to your Inbox.