[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Bug fix: list? now O(log n)

This page is part of the web mail archives of SRFI 101 from before July 7th, 2015. The new archives for SRFI 101 contain all messages, not just those from before July 7th, 2015.



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