On the contrary, car and cdr are GUARANTEED to be O(1). car == return the first element in a pair. cdr == return the second element in a pair.
The fact that the cdr of a list returns the rest of the list is simply an incidental side-effect of the definition of list. Cheers, Daniel. On 7 March 2014 18:28, Deren Dohoda <deren.doh...@gmail.com> wrote: > Does this mean we shouldn't cdr functional lists but only use rest? > On Mar 7, 2014 12:02 PM, "Matthias Felleisen" <matth...@ccs.neu.edu> > wrote: > >> >> In a world of immutable cons-es you can cache the result so that testing >> list? becomes an O(1) operation. >> >> >> >> >> On Mar 7, 2014, at 11:52 AM, Eric Dong <yd2d...@uwaterloo.ca> 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? >> > >> > >> > On Fri, Mar 7, 2014 at 10:16 AM, Daniel Carrera <dcarr...@gmail.com> >> wrote: >> > Ok. That makes sense. A list is either '() or something plus a list. >> > >> > Thanks. >> > >> > Cheers, >> > Daniel. >> > >> > >> > On 7 March 2014 14:46, Jon Zeppieri <zeppi...@gmail.com> wrote: >> > Oops, sorry about that empty message. I was going to say that your >> > definition of a list is close, but it's missing something, A list is >> > either: >> > >> > - the empty list; or >> > - a pair, the second element of which is a list >> > >> > (cons 3 2) is a pair, and sometimes non-list pairs are called >> > "improper lists," but they don't satisfy list?. >> > >> > >> > On Fri, Mar 7, 2014 at 8:43 AM, Jon Zeppieri <zeppi...@gmail.com> >> wrote: >> > > On Fri, Mar 7, 2014 at 8:39 AM, Daniel Carrera <dcarr...@gmail.com> >> wrote: >> > >> What is (cons 3 2) ? What is the definition of a list? I thought >> that a list >> > >> was defined as either '() or a pair. >> > >> >> > >> Cheers, >> > >> Daniel. >> > >> >> > >> >> > >> On 7 March 2014 13:49, Jens Axel Søgaard <jensa...@soegaard.net> >> wrote: >> > >>> >> > >>> The value (cons 3 42) is not a list. The function car will extract >> 3, >> > >>> but first will fail. >> > >>> >> > >>> /Jens Axel >> > >>> >> > >>> >> > >>> 2014-03-07 13:40 GMT+01:00 Daniel Carrera <dcarr...@gmail.com>: >> > >>> > Thanks. That's a very useful tip (being able to get at the source >> code). >> > >>> > I >> > >>> > am a bit confused by the condition "(and (pair? x) (list? x))". >> It seems >> > >>> > to >> > >>> > me that this could just be replaced with "(pair? x)". The "list?" >> > >>> > doesn't >> > >>> > add anything. Am I wrong? >> > >>> > >> > >>> > Also, I don't see exactly how "first" and "car" behave different >> on a >> > >>> > non-list. They both raise an error. The errors are just worded >> > >>> > differently. >> > >>> > >> > >>> > On the same file, I found the definition of empty? >> > >>> > >> > >>> > (define empty? (lambda (l) (null? l))) >> > >>> > >> > >>> > Wouldn't it be more economical to write "(define empty? null?)" >> and >> > >>> > allow >> > >>> > them to be synonyms? >> > >>> > >> > >>> > Cheers, >> > >>> > Daniel. >> > >>> > >> > >>> > >> > >>> > On 7 March 2014 12:16, Jens Axel Søgaard <jensa...@soegaard.net> >> wrote: >> > >>> >> >> > >>> >> For lists first/rest works the same as car/cdr. >> > >>> >> For non-lists there is a difference: first and rest signals an >> error. >> > >>> >> The names first and rest makes it easier for a human reader of >> > >>> >> a piece of code to see that the program works on lists only. >> > >>> >> >> > >>> >> For the curious, the definition of first is: >> > >>> >> >> > >>> >> (define (first x) >> > >>> >> (if (and (pair? x) (list? x)) >> > >>> >> (car x) >> > >>> >> (raise-argument-error 'first "(and/c list? (not/c empty?))" >> x))) >> > >>> >> >> > >>> >> I found this definition like this: >> > >>> >> 1. Entered this program in DrRacket: >> > >>> >> #lang racket >> > >>> >> first >> > >>> >> 2. Clicked the "Check Syntax" button >> > >>> >> 3. Right clicked the identifier first and chose "Open defining >> file" >> > >>> >> 4. Chose "first" in the definition-drop-down in the upper left >> corner. >> > >>> >> >> > >>> >> /Jens Axel >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> 2014-03-07 11:45 GMT+01:00 Daniel Carrera <dcarr...@gmail.com>: >> > >>> >> > Hello, >> > >>> >> > >> > >>> >> > Is there any difference between `first` and `car`, or between >> `last` >> > >>> >> > and >> > >>> >> > `cdr`, or between `empty? and null?` ? >> > >>> >> > >> > >>> >> > I had assumed that these were just synonyms, added by Racket >> because >> > >>> >> > they >> > >>> >> > might be more memorable to a student. But apparently Racket >> doesn't >> > >>> >> > think >> > >>> >> > they are equal: >> > >>> >> > >> > >>> >> > -> (equal? first car) >> > >>> >> > #f >> > >>> >> > -> (equal? last cdr) >> > >>> >> > #f >> > >>> >> > -> (equal? empty? null?) >> > >>> >> > #f >> > >>> >> > >> > >>> >> > >> > >>> >> > I suppose that they could be separate functions that happen to >> do the >> > >>> >> > same >> > >>> >> > thing, but if so, my next question would be why they aren't >> just >> > >>> >> > aliases. As >> > >>> >> > in: >> > >>> >> > >> > >>> >> > -> (define myfirst car) >> > >>> >> > -> (equal? myfirst car) >> > >>> >> > #t >> > >>> >> > >> > >>> >> > Cheers, >> > >>> >> > Daniel. >> > >>> >> > -- >> > >>> >> > When an engineer says that something can't be done, it's a code >> > >>> >> > phrase >> > >>> >> > that >> > >>> >> > means it's not fun to do. >> > >>> >> > >> > >>> >> > ____________________ >> > >>> >> > Racket Users list: >> > >>> >> > http://lists.racket-lang.org/users >> > >>> >> > >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> -- >> > >>> >> -- >> > >>> >> Jens Axel Søgaard >> > >>> > >> > >>> > >> > >>> > >> > >>> > >> > >>> > -- >> > >>> > When an engineer says that something can't be done, it's a code >> phrase >> > >>> > that >> > >>> > means it's not fun to do. >> > >>> >> > >>> >> > >>> >> > >>> -- >> > >>> -- >> > >>> Jens Axel Søgaard >> > >> >> > >> >> > >> >> > >> >> > >> -- >> > >> When an engineer says that something can't be done, it's a code >> phrase that >> > >> means it's not fun to do. >> > >> >> > >> ____________________ >> > >> Racket Users list: >> > >> http://lists.racket-lang.org/users >> > >> >> > >> > >> > >> > -- >> > When an engineer says that something can't be done, it's a code phrase >> that means it's not fun to do. >> > >> > ____________________ >> > Racket Users list: >> > http://lists.racket-lang.org/users >> > >> > >> > ____________________ >> > Racket Users list: >> > http://lists.racket-lang.org/users >> >> >> ____________________ >> Racket Users list: >> http://lists.racket-lang.org/users >> > > ____________________ > Racket Users list: > http://lists.racket-lang.org/users > > -- When an engineer says that something can't be done, it's a code phrase that means it's not fun to do.
____________________ Racket Users list: http://lists.racket-lang.org/users
