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 ____________________ Racket Users list: http://lists.racket-lang.org/users
