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

On Sat, Mar 08, 2014 at 11:10:20AM -0700, Matthew Flatt wrote:
> At Sat, 08 Mar 2014 12:33:42 -0500, "David T. Pierson" wrote:
> >   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

Ah, that makes sense.  And now that I look closely, I see that the time
was decreasing by about half each time.

Thanks.

David