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

From: Pierpaolo Bernardi (olopierpa at gmail.com)
Date: Tue May 15 04:06:23 EDT 2012

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
> (test (expt 10 7) 1000)
cpu time: 109 real time: 109 gc time: 0

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.



Posted on the users mailing list.