[racket] first vs car ; last vs cdr ; empty? vs null?

I'm joining in this thread because I'm now wondering about the same questions.

It seems to me that if a list is created via list or make-list then the bits should have been set on the car of the new list, so all the list predicates have to do is check the first element in O(1) time.

Likewise cons can check to see if the second element is a list and correspondingly set bits on the first element.

Thanks to immutable pairs, it seems it should be possible to provide guarantees on list? being always O(1) by using the above technique without needing to cache results and converging to O(1) in the limit.



> On Mar 8, 2014, at 12:33 PM, "David T. Pierson" <dtp at mindstory.com> wrote:
> 
>> On Fri, Mar 07, 2014 at 11:03:57PM -0500, Carl Eastlund wrote:
>> The first/rest operations do not use a memoization table.  They test using
>> the list? primitive, which is built in and actually has a couple of tag
>> bits reserved on every cons object for memoizing its results.  So the
>> operation really is quite fast.
> 
> I take this to mean there is a bit in the cons object for storing
> whether it is a list, and that this bit is set via `list?'.
> 
> Why wouldn't the bit be set via `cons'?
> 
> Also, when I do:
> 
>  $ racket
>  Welcome to Racket v6.0.0.2.
>> (let ((ls (make-list 50000000 0)))
>    (time (list? ls))                                                                                             
>    (time (list? ls))                                                                                             
>    (time (list? ls))                                                                                             
>    (time (list? ls))                                                                                             
>    (time (list? ls)))
> 
>  cpu time: 220 real time: 220 gc time: 0
>  cpu time: 112 real time: 112 gc time: 0
>  cpu time: 60 real time: 58 gc time: 0
>  cpu time: 28 real time: 29 gc time: 0
>  cpu time: 16 real time: 15 gc time: 0
>  #t
> 
> Why does the time decrease gradually, rather than the 2nd and subsequent
> times being roughly equivalent?
> 
> Thanks.
> 
> David
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users