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

From: David Van Horn (dvanhorn at cs.umd.edu)
Date: Fri Mar 7 12:02:16 EST 2014

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


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


Posted on the users mailing list.