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

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