[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