[plt-scheme] Making a fast list like sequence

At Tue, 7 Apr 2009 18:55:40 -0400, Carl Eastlund wrote:
> On Tue, Apr 7, 2009 at 6:48 PM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> > At Tue, 07 Apr 2009 18:32:33 -0400, David Van Horn wrote:
> >> I see dramatic differences in running times between the built-in list
> >> sequence and a naive implementation of list sequencing.  What can I do
> >> to make this naive implementation run faster?
> >
> > If you use use `car', `cdr', and `pair? instead of `first', `rest', and
> > `(compose not empty?)', you should get the same performance as for
> > lists.
> 
> I can certainly see why pair? will be faster than (compose not
> empty?), but why would car/cdr/pair?/null? be significantly faster
> than first/rest/cons?/empty? ?  Is there extra contract wrapping or
> something?

The `first' and `rest' functions work only on lists, so there's an
extra test. The test is constant-time due to immutable pairs, but it's
still extra compared to `car' and `cdr'.