From: Will Hartung
Subject: Re: newbie: what are 'first' and 'rest' procedures.
Date:
Message-ID: <vfr750EEq4FG.7BE@netcom.com>
Mitch <·······@psnw.com> writes:
>Can anyone explain to me what are 'first' and 'rest' procedures? Please
>help.
Poor Mitch, or Vincent... (I'll call you Mitch, just like my
newsreader does.)
I do give him an 'A' for tenacity.
You REALLY REALLY REALLY need to find a beginning text of Lisp/Scheme.
It will open your eyes very wide. The Lisp FAQ lists several.
"Scheme and the Art of Programming" is nice, so is "Simply Scheme",
and "The Little Schemer".
Now, on to your questions.
Technically, 'first' returns the first element of a list, and 'rest'
returns all BUT the first element of the list. A list being a linkage
of cons cells.
Another way to look at it is:
first = car
rest = cdr
'first' and 'rest' represent the two halves of what is called a 'cons'
cell. For historical reason, those two pieces are primarily known as
'car' and 'cdr'.
The two pieces of a cons cell can reference anything they want.
However, they are most often found in lists.
Let's consider the list (a b c d).
This list is built up of 4 cons cells. Let's number the cons cells
1,2,3 and 4.
The 'car' (or 'first') of each cons cell is a reference to a data
element (the symbols a,b,c and d in this case). The 'cdr' (or 'rest')
of each cons cell references another cons cell, except for cons cell
#4, which references 'nil'.
The procedure 'cons' creates a cons cell, and its two arguments are
the car and cdr of the cell.
One way to create our list is:
> (cons 'a (cons 'b (cons 'c (cons 'd nil))))
(a b c d)
But, look at this also:
> (cons (cons (cons (cons nil 'd) 'c) 'b) 'a)
((((nil . d) . c) . b) . a)
In many ways, this list and the other are the same. The difference is
that in the first list, the 'cdr' of the cons cell is used to link to
the rest of the list, whereas in the second structure, the 'car' is
used as the link. Lisp/Scheme "knows" about the first structure, and
doesn't print the dots and the nil, whereas it doesn't "know" about
the second, so it shows everything. Also, the second one looks
"backward", but that is because of the way the Lisp printer decides to
print things. If you study it, you'll notice that the first cons cell
of each list contains 'a.
Look at this simple function to count elements (in Scheme):
(define (my-cdr-count cdr-list)
(if (null? cdr-list)
0
(+ 1 (my-cdr-count (cdr cdr-list)))))
This works on you standard, generic list. Now try:
(define (my-car-count car-list)
(if (null? car-list)
0
(+ 1 (my-car-count (car car-list)))))
This will only work on the second list.
So, look at this little table:
'(a b c d) represents 4 cons cells.
Cons # car cdr
-------+------+----
Cell 1 | 'a | links to Cell 2
Cell 2 | 'b | links to Cell 3
Cell 3 | 'c | links to Cell 4
Cell 4 | 'd | nil
Whereas:
'(a . b) represents 1 cons cell. You can tell because of the dot(.).
Cons # car cdr
-------+------+----
Cell 1 | 'a | 'b
What is interesting, and perhaps confusing, is that 'car' and 'cdr'
represent the cons cell directly. When cons cells are linked together,
the system is "aware" of this relationship, and we call it a 'list'
However, there is nothing stopping you from using a cons cell as a two
part structure for anything you want.
Whereas 'first' and 'rest' are, at least conceptually, designed to
represent a list. 'first' and 'rest' don't say anything about how the
list is constructed, just that the 'first' procedure gives you the
first element of the list, and 'rest' give you everything BUT the first
element of the list, regardless how it's organized. Another name, perhaps
better, for 'rest' is 'but-first', as that is exactly what it does.
Typically this is all shown using boxes and lines and paper, but I'm
not up to drawing ascii box graphs right now.
I may have just muddied the water for you, but I hope that this gives
you a better idea of how things are laid out in simple Lisp/Scheme
system.
Feel free to ask more questions, but do yourself a favor and get your
hands on a decent book -- those authors get paid to write clearly,
whereas I just make this stuff up as I go. And then what is worse, is
I go back and 'edit' it. Oh dear. :-)
Luck!
--
Will Hartung - Rancho Santa Margarita. It's a dry heat. ······@netcom.com
1990 VFR750 - VFR=Very Red "Ho, HaHa, Dodge, Parry, Spin, HA! THRUST!"
1993 Explorer - Cage? Hell, it's a prison. -D. Duck
From: Emergent Technologies Inc.
Subject: Re: newbie: what are 'first' and 'rest' procedures.
Date:
Message-ID: <5solqh$2tc$2@newsie2.cent.net>
Mitch wrote in article <·················@psnw.com>...
>Can anyone explain to me what are 'first' and 'rest' procedures? Please
>help.
Sure. first and rest are procedures that operate on lists. first returns
the first element of a list and rest returns the remaining elements.
Examples:
(define l '(a b c d e))
(first l) -> a
(rest l) -> (b c d e)