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

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.dohoda at 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" <matthias at 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 <yd2dong at 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 <dcarrera at 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 <zeppieri at 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 <zeppieri at gmail.com>
>> wrote:
>> > > On Fri, Mar 7, 2014 at 8:39 AM, Daniel Carrera <dcarrera at 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 <jensaxel at 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 <dcarrera at 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 <jensaxel at 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 <dcarrera at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140307/74b849c8/attachment.html>