FWIW, the list? check that is inside first and rest caches its result in the header information in the cons cells it traverses.
Robby On Tue, May 15, 2012 at 3:06 AM, Pierpaolo Bernardi <olopie...@gmail.com> wrote: > On Mon, May 14, 2012 at 8:16 PM, Jay McCarthy <jay.mccar...@gmail.com> wrote: >> They could be identical, but they are different because one set is >> about lists and the other is about pairs. The fact that pairs may be >> used to implement lists is immaterial. >> >> You should really never use the c[ad]*r functions unless you are >> specifically dealing with pairs. > > So, what should one use on proper lists? > > - c[ad]*r no; > - first and rest appear to be O(n): > > #lang racket > > (define (test len times) > (let ((ll (make-list len 1))) > (time (for/sum ((i (in-range times))) > (+ (first ll) > (second ll)))))) > >> (test (expt 10 6) 1000) > cpu time: 15 real time: 16 gc time: 0 > 2000 >> (test (expt 10 7) 1000) > cpu time: 109 real time: 109 gc time: 0 > 2000 > > Why this check is made only for first, rest, etc, and not for all the > functions that take a list? > > For example, (list-ref list 1) appears to be O(1) in the length of list. > > ? > > P. > ____________________ > Racket Users list: > http://lists.racket-lang.org/users ____________________ Racket Users list: http://lists.racket-lang.org/users
