Bug fix: list? now O(log n) David Van Horn 19 Sep 2009 14:08 UTC

I noticed a really dumb bug in the reference implementation for list?,
which the document requires to be O(log n), where n is the count of the
chain of pairs in the input.  Instead the implementation was naively
traversing through the list of elements instead of just the forest of
trees.  This will be fixed in the next revision, but the change is the
following:

   ;; [Any -> Boolean]
   ;; Is x a PROPER list?
   (define (ra:list? x)
     (or (ra:null? x)
         (and (ra:pair? x)
              (ra:list? (ra:cdr x)))))

To:

   ;; [Any -> Boolean]
   ;; Is x a PROPER list?
   (define (ra:list? x)
     (or (ra:null? x)
         (and (kons? x)
              (ra:list? (kons-rest x)))))

David