Ray Dillinger scripsit: > Implentations may signal an error, but the cost of doing so (especially > in the case where there is no error) would be high.
Actually, it's not *that* high. Algorithms that are O(n) remain O(n); it's just that they have to read the whole list instead of just some part of it, half of it on average. In particular, the naive implementation of memq (checking just for the null list as termination) will throw a "car: not a pair" style error if it runs off the end, which is doubtless why and how most of my Schemes terminate. If you test for not-a-cons as termination, you get #f. SRFI 1 has a nice predicate `null-list?` which returns #t on (), #f on a pair, and an error on anything else (the SRFI says "is an error" but the reference implementation actually raises one). This also appears in Common Lisp as ENDP. -- Where the wombat has walked, John Cowan <[email protected]> it will inevitably walk again. http://www.ccil.org/~cowan (even through brick walls!) _______________________________________________ Scheme-reports mailing list [email protected] http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports
