<div dir="ltr">On the contrary, car and cdr are GUARANTEED to be O(1).<div> </div><div>car == return the first element in a pair.</div><div>cdr == return the second element in a pair.</div><div> </div><div>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.</div> <div> </div><div>Cheers,</div><div>Daniel. <div class="gmail_extra"> <div class="gmail_quote">On 7 March 2014 18:28, Deren Dohoda <<a href="mailto:deren.dohoda@gmail.com" target="_blank">deren.dohoda@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Does this mean we shouldn't cdr functional lists but only use rest? <div class="gmail_quote">On Mar 7, 2014 12:02 PM, "Matthias Felleisen" <<a href="mailto:matthias@ccs.neu.edu" target="_blank">matthias@ccs.neu.edu</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> 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 <<a href="mailto:yd2dong@uwaterloo.ca" target="_blank">yd2dong@uwaterloo.ca</a>> 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 <<a href="mailto:dcarrera@gmail.com" target="_blank">dcarrera@gmail.com</a>> 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 <<a href="mailto:zeppieri@gmail.com" target="_blank">zeppieri@gmail.com</a>> 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 <<a href="mailto:zeppieri@gmail.com" target="_blank">zeppieri@gmail.com</a>> wrote: > > On Fri, Mar 7, 2014 at 8:39 AM, Daniel Carrera <<a href="mailto:dcarrera@gmail.com" target="_blank">dcarrera@gmail.com</a>> 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 <<a href="mailto:jensaxel@soegaard.net" target="_blank">jensaxel@soegaard.net</a>> 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 <<a href="mailto:dcarrera@gmail.com" target="_blank">dcarrera@gmail.com</a>>: > >>> > 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 <<a href="mailto:jensaxel@soegaard.net" target="_blank">jensaxel@soegaard.net</a>> 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 <<a href="mailto:dcarrera@gmail.com" target="_blank">dcarrera@gmail.com</a>>: > >>> >> > 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: > >>> >> > <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a> > >>> >> > > >>> >> > >>> >> > >>> >> > >>> >> -- > >>> >> -- > >>> >> 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: > >> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a> > >> > > > > -- > 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: > <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a> > > > ____________________ > Racket Users list: > <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a> ____________________ Racket Users list: <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a> </blockquote></div> ____________________ Racket Users list: <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a> </blockquote></div> <div> </div>-- When an engineer says that something can't be done, it's a code phrase that means it's not fun to do. </div></div></div>