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

Bug fix: list? now O(log n)



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