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

On 3/7/14, 11:52 AM, Eric Dong wrote:
> Forgive me if I am super terribly wrong. Isn't it the case that an improper
> list is only known to be improper if we walk to the end and find something
> other than an empty? So wouldn't that mean "first" and "rest" take linear
> time since they must make sure the argument is a list? Clearly that doesn't
> happen. What am I missing?


That's correct.

What you're missing is that the cost is amortized.  It gets cheaper to
check the more times you check it.  In the limit, it's a constant time
operation.

Eg:

(let ((ls (make-list 50000000 0)))
  (time (list? ls))
  (time (list? ls))
  (time (list? ls))
  (time (list? ls))
  (time (list? ls)))

David