Re: [Scheme-reports] Query - Pairs and Lists

[John Cowan <cowan@x>]

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 <cowan@x>
it will inevitably walk again.          http://www.ccil.org/~cowan
   (even through brick walls!)

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports