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

At Sat, 08 Mar 2014 12:33:42 -0500, "David T. Pierson" wrote:
> 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?

When `list?` explores N pairs to determine whether its argument is a
list, it sets a bit once after N/2 pairs. That choice avoids the cost
of setting bits everywhere while providing amortized constant time for
`rest` in something like

 (define (len l)
   (if (empty? l)
       0
       (add1 (len (rest l)))))

Setting the bit at N/2 pairs also happens to reuse references that are
already in flight for tortoise--hare cycle detection. (Whether it's
worth having immutable cyclic pairs is yet another question, though.)