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

At Tue, 15 May 2012 06:31:13 -0500, Robby Findler wrote:
> FWIW, the list? check that is inside first and rest caches its result
> in the header information in the cons cells it traverses.

In other words, `first and `rest' are amortized constant-time, due to
the use of the amortized constant-time `list?'.

You can think of the cost of `list?' as being charged to the list
creation, and each single list creation n your example takes about 10
times as long as the 1000 accesses, so the cost is very small overall.
In particular, if you add a second sum loop on the same list, it takes
the same amount of time for both.

For example, with

 #lang racket

 (define (test len times)
   (let ((ll (time (make-list len 1))))
     (time (for/sum ((i (in-range times)))
                    (+ (first ll)
                       (second ll))))
     (time (for/sum ((i (in-range times)))
                    (+ (first ll)
                       (second ll))))))

 (test (expt 10 6) 100000)
 (test (expt 10 7) 100000)

I get

 cpu time: 74 real time: 75 gc time: 63
 cpu time: 14 real time: 15 gc time: 0
 cpu time: 5 real time: 5 gc time: 0
 200000
 cpu time: 1429 real time: 1433 gc time: 1342
 cpu time: 98 real time: 98 gc time: 0
 cpu time: 4 real time: 5 gc time: 0
 200000

Some functions, such as `list-ref', do not have a `list?' contract
because they are intended to work on more values than lists --- which
means that some of them, like `list-ref', are at this point misnamed.


> 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.