[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