[racket] first and rest etc. only work on proper lists

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 <olopierpa at gmail.com> wrote:
> On Mon, May 14, 2012 at 8:16 PM, Jay McCarthy <jay.mccarthy at 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