newbie take: what Lisp's lists are good at
verec
the idea that Lisp's lists are both necessary and not
the only game in town.
This is from the perspective of a newbie (myself) who
went through the successive learning phases of:
1 lists are complicated and daunting. And who needs
a cons anyway?
2 lists are the skeleton upon which the entire Lisp
language/engine is built. Whenever you (defun or
(defmacro you're just creating some kind of list.
Your source code is a long suite of lists.
3 for all their merit, lists are not appropriate for
every single kind of use. Other data structures
exist that are most always a better map to the
problem at hand, be it hash-table, arrays, strings,
structure or even classes...
Here am I, in this stage 3: lists for all the code
itself, lists for data sometimes, anything other than
list when appropriate.
Lists are a good match for recursion, and thus for
"functional programming" because lists can contain
lists. But so do arrays (which can contain other
arrays, up to at least ARRAY-RANK-LIMIT levels of
nesting) hash-tables, which can contain other hash-tables
or even instances of classes that can go to any arbitray
level of nesting.
So, being a "good match" for recursive algorithms is
not an attribute unique to lists, though the splitting
of lists along the lines of "first-item-of" and "rest-of"
(car and cdr) certainly makes the coding far easier than
doing the same for arrays, hash-table, etc...
A way to do this with arrays would be to create one
dimensional arrays, whose contents could either be
other (one dimensional) arrays or the atom we want to
deal with:
CL-USER 1 > (defun car-array (array)
(aref array 0))
car-array
CL-USER 2 > (defun cdr-array (array) ; undefined when (< (length array) 1)
(make-array (1- (array-dimension array 0))
:element-type (array-element-type array)
:displaced-to array
:displaced-index-offset 1))
cdr-array
CL-USER 3 > #1a(1 3 5 7 9)
#(1 3 5 7 9)
CL-USER 4 > (car-array *)
1
CL-USER 5 > (cdr-array **)
#(3 5 7 9)
But then, as much as lists don't scale too well as hash-tables,
arrays seem quite overkill and inefficient when linked lists are
just right.
--
JFB
Ulrich Hobelmann
> 1 lists are complicated and daunting. And who needs
> a cons anyway?
For me that phase was: recursion takes some getting used to. OTOH,
often there are more convenient ways to construct lists, such as LOOP
with a COLLECT clause.
Accessing list items isn't that hard, either, nor is traversing them.
> Lists are a good match for recursion, and thus for
> "functional programming" because lists can contain
> lists. But so do arrays (which can contain other
> arrays, up to at least ARRAY-RANK-LIMIT levels of
> nesting) hash-tables, which can contain other hash-tables
> or even instances of classes that can go to any arbitray
> level of nesting.
Lists are very convenient for stuff with variable size, such as
filtering a sequence, when you don't know with how many items you're
gonna end up. Arrays are cool and fast if you need to process bunches
of uniform data.
> So, being a "good match" for recursive algorithms is
> not an attribute unique to lists, though the splitting
> of lists along the lines of "first-item-of" and "rest-of"
> (car and cdr) certainly makes the coding far easier than
> doing the same for arrays, hash-table, etc...
Inside a LOOP lists and arrays are pretty much the same to loop over...
--
The problems of the real world are primarily those you are left with
when you refuse to apply their effective solutions.
Edsger W. Dijkstra
Jens Axel Søgaard
> I'm trying here to find the right wording to express
> the idea that Lisp's lists are both necessary and not
> the only game in town.
See also:
<http://en.wikipedia.org/wiki/Linked_list>
--
Jens Axel Søgaard
Brian Downing
verec <ve...@mac.com> wrote:
> Lists are a good match for recursion, and thus for
> "functional programming" because lists can contain
> lists. But so do arrays (which can contain other
> arrays, up to at least ARRAY-RANK-LIMIT levels of
> nesting)
Arrays can contain other arrays until your memory fills up.
ARRAY-RANK-LIMIT is for multidimensional arrays, which are not the same
as arrays-containing-arrays.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Brian Downing
Brian Downing <see-si...@lavos.net> wrote:
> Arrays can contain other arrays until your memory fills up.
> ARRAY-RANK-LIMIT is for multidimensional arrays, which are not the same
> as arrays-containing-arrays.
Obligatory stupid example:
CL-USER> array-rank-limit
253
CL-USER> (setf *print-circle* t)
T
CL-USER> (defparameter *infinite* #1=#(#1# #1#))
*INFINITE*
CL-USER> (aref (aref (aref *infinite* 0) 1) 0)
#1=#(#1# #1#)
CL-USER> (let ((infinite *infinite*))
(dotimes (i 1000000 infinite)
(setf infinite (aref infinite (random 2)))))
#1=#(#1# #1#)
:-)
(For additional stupidity, try:
CL-USER> #1=#0A#1#
#1=#0A#1#
CL-USER> (aref *)
#1=#0A#1#
CL-USER> (array-rank *)
0
Works in SBCL, doesn't work in Lispworks.)
Bill Atkins
> I'm trying here to find the right wording to express
> the idea that Lisp's lists are both necessary and not
> the only game in town.
Of course.
> This is from the perspective of a newbie (myself) who
> went through the successive learning phases of:
>
> 1 lists are complicated and daunting.
What's complicated about them?
> And who needs
> a cons anyway?
Everyone needs conses - any singly-linked list needs to use a pair
structure to hold data and a pointer to the next item. Defining a node
structure in C is equivalent to using a cons.
> 2 lists are the skeleton upon which the entire Lisp
> language/engine is built. Whenever you (defun or
> (defmacro you're just creating some kind of list.
> Your source code is a long suite of lists.
>
> 3 for all their merit, lists are not appropriate for
> every single kind of use. Other data structures
> exist that are most always a better map to the
> problem at hand, be it hash-table, arrays, strings,
> structure or even classes...
No kidding?
But this is silly. If you're going to be using arrays this way, why
not use lists? Keep in mind that a list can do everything an array can
do - it's just that getting its length and accessing a random element
are linear rather than constant-time operations. If you find yourself
needing car-array and cdr-array, an array may not be the most
appropriate data structure for you.
> But then, as much as lists don't scale too well as hash-tables,
> arrays seem quite overkill and inefficient when linked lists are
> just right.
> --
> JFB
--
Bill Atkins
"The REPL is my shepherd; I shall not want. It maketh me to lie down
among the parens, It leadeth me beside the generic functions and the
multimethods. It restoreth my soul; It leadeth me in the paths of
interactive development for my sanity's sake. Yea, though I walk
through the valley of the shadow of syntax, I will fear no evil, for
thou art with me; thy s-expression and thy parenthesis they comfort me.
Thou preparest a core image before me in the presence of mine enemies;
thou anointest my code with syntactic abstraction; my cup runneth over.
Surely quick development time and flawless code shall follow me all the
days of my life and I will dwell in the house of the REPL for ever."
-- Psalm 23 (adapted)
verec
> In article <43c91738$0$87299$5a6a...@news.aaisp.net.uk>,
> verec <ve...@mac.com> wrote:
>> Lists are a good match for recursion, and thus for
>> "functional programming" because lists can contain
>> lists. But so do arrays (which can contain other
>> arrays, up to at least ARRAY-RANK-LIMIT levels of
>> nesting)
>
> Arrays can contain other arrays until your memory fills up.
True. But so it is with cons too. Correct me if I'm wrong,
but I thought that the GC didn't care at all whether a chunk
of bytes to be recycled was a cons or an array, ie, I expect
both of
CL-USER 1 > #1a(1 2 3)
#(1 2 3)
CL-USER 2 > '(1 2 3)
(1 2 3)
to be GC'd away as soon as *, ** and *** stop referring to
them.
> ARRAY-RANK-LIMIT is for multidimensional arrays,
> which are not the same as arrays-containing-arrays.
True too, but as far as recursion is concerned, they're
both an instance of the same idea: a 2 dimensional array
can be seen as a 1 dimensional array whose elements are
rows (columns) each of which being itself an array of
"primitive" types.
Sure, Lisp provides a syntax that is different in both
cases, ie (aref a x y) vs (aref (aref a x) y), but the
idea is the same.
--
JFB
verec
>> CL-USER 1 > (defun car-array (array)
>> (aref array 0))
>> car-array
>> CL-USER 2 > (defun cdr-array (array) ; undefined when (< (length array) 1)
>> (make-array (1- (array-dimension array 0))
>> :element-type (array-element-type array)
>> :displaced-to array
>> :displaced-index-offset 1))
>> cdr-array
>> CL-USER 3 > #1a(1 3 5 7 9)
>> #(1 3 5 7 9)
>> CL-USER 4 > (car-array *)
>> 1
>> CL-USER 5 > (cdr-array **)
>> #(3 5 7 9)
>
> But this is silly. If you're going to be using arrays this way, why
> not use lists? Keep in mind that a list can do everything an array can
> do - it's just that getting its length and accessing a random element
> are linear rather than constant-time operations. If you find yourself
> needing car-array and cdr-array, an array may not be the most
> appropriate data structure for you.
The point was certainly not to advocate the use of arrays
as a subsitute for lists when lists are perfectly appropriate
as the subsequent praragraph did state:
>> But then, as much as lists don't scale too well as hash-tables,
>> arrays seem quite overkill and inefficient when linked lists are
>> just right.
But rather to show that there was nothing magic about car
and cdr, and that one could, in principle, implement them
using any data structure other than conses, even though doing
so might not be the best practical idea.
Also, this underlines the fact that "first" and "rest" are the
linchpin on which to build recursive definitions applying
to sequences, whether such a sequence is a list or an array,
and that, should the need arise, it seems possible to define
them for sequences that are not linked lists, as in the example.
--
JFB
Pascal Bourguignon
> Sure, Lisp provides a syntax that is different in both
> cases, ie (aref a x y) vs (aref (aref a x) y), but the
> idea is the same.
Indeed, you should have a look at my -> syntax!
Use: (-> a x y) in both cases, and even with other stuff than arrays.
(defun length<= (length list)
(or (zerop length) (and list (length<= (1- length) (cdr list)))))
(defun -> (object &rest path)
(cond
((null path) object)
((arrayp object)
(let ((d (array-rank object)))
(if (length<= d path)
(apply (function ->)
(apply (function aref) object (subseq path 0 d))
(nthcdr d path))
(make-array ; let's get a slice
(nthcdr (length path) (array-dimensions object))
:displaced-to object
:displaced-index-offset
(apply (function array-row-major-index) object
(append path (make-list (- d (length path))
:initial-element 0)))
:element-type (array-element-type object)))))
((and (listp object)
(every (function consp) object)
(not (integerp (first path))))
(apply (function ->) (cdr (assoc (first path) object)) (rest path)))
((listp object)
(apply (function ->) (elt object (first path)) (rest path)))
((hash-table-p object)
(apply (function ->) (gethash (first path) object) (rest path)))
((typep object '(or structure-object standard-object))
(apply (function ->) (funcall (first path) object) (rest path)))
((or (functionp (first path))
(and (symbolp (first path)) (fboundp (first path))))
(apply (function ->) (funcall (first path) object) (rest path)))
(t (error "This is not a compound object: ~S" object))))
;; defsetf left as exercise to the reader ;-)
[95]> (-> (make-array '(2 2) :initial-contents '((1 2)(3 4))) 0 1)
2
[96]> (-> (make-array 2 :initial-contents
(list (make-array 2 :initial-contents '(1 2))
(make-array 2 :initial-contents '(3 4)))) 0 1)
2
--
__Pascal Bourguignon__ http://www.informatimago.com/
Cats meow out of angst
"Thumbs! If only we had thumbs!
We could break so much!"
verec
> verec <ve...@mac.com> writes:
>> Sure, Lisp provides a syntax that is different in both
>> cases, ie (aref a x y) vs (aref (aref a x) y), but the
>> idea is the same.
>
> Indeed, you should have a look at my -> syntax!
>
> Use: (-> a x y) in both cases, and even with other stuff than arrays.
Waahhooo!
I follow the first two cond cases, but I'm a bit
puzzled by the rest ...
I tried (and traced)
CL-USER 18 > (-> nil '(+ 1 2 3))
NIL
just to see what would happen, but I must admit I'm none
the wiser )-:
A great puzzle for the rest of the week-end! Thanks :-)
> ;; defsetf left as exercise to the reader ;-)
:-(
--
JFB
verec
> Inside a LOOP lists and arrays are pretty much the same to loop over...
Thanks. But I'm not ready for "loop" yet! I must admit of
the charm of the "collect" form, but that's for ... phase 4! :-)
--
JFB
verec
> See also:
> <http://en.wikipedia.org/wiki/Linked_list>
Thanks
--
JFB
Pascal Bourguignon
> On 2006-01-15 02:46:32 +0000, Pascal Bourguignon <sp...@mouse-potato.com> said:
>
>> verec <ve...@mac.com> writes:
>>> Sure, Lisp provides a syntax that is different in both
>>> cases, ie (aref a x y) vs (aref (aref a x) y), but the
>>> idea is the same.
>> Indeed, you should have a look at my -> syntax!
>> Use: (-> a x y) in both cases, and even with other stuff than
>> arrays.
>
> Waahhooo!
>
> I follow the first two cond cases, but I'm a bit
> puzzled by the rest ...
>
> I tried (and traced)
>
> CL-USER 18 > (-> nil '(+ 1 2 3))
> NIL
(defun +/ (args) (apply (function +) args))
(-> '(1 2 3) +/)
-> has a postfix grammar: (-> object selector ...)
The selector is usually an index or a key, but can be a unary function
applied to the current object. Each selector is applied in order to
the result of the following selector.
> just to see what would happen, but I must admit I'm none
> the wiser )-:
>
> A great puzzle for the rest of the week-end! Thanks :-)
Other usage patterns:
(defstruct s h l a s)
(defclass c () ((f :accessor f :initarg :f) (g :accessor g :initarg :g)))
(let* ((h (make-hash-table))
(s (make-instance 'c
:f (list (make-s :h h :l '((:a . 1) (:b . 2) (:c . 3))
:a #2A((1 2) (3 4)) :s "Hello")
(make-s :h h :l '((:a . 10) (:b . 20) (:c . 30))
:a #2A((1 2 3) (4 5 6) (7 8 9)) :s "world"))
:g '((* 2 x x) (* 4 x) 3))))
(setf (gethash 'x h) #(a b c)
(gethash 'y h) #(d e f))
(with-input-from-string (stream "Iteration objects structures conditions")
(values
(-> #2A((1 2 3) (4 5 6) (7 8 9)) 1 2)
(-> #2A((1 2 3) (4 5 6) (7 8 9)) 1)
(-> h 'x)
(-> 'h 'symbol-name)
(-> "Hello" 1)
;; (-> "Hello" 'string-upcase) ; not yet
(-> :cl-user 'package-nicknames)
(-> :cl-user 'package-nicknames 1)
(-> :cl-user 'package-nicknames 1 0)
(-> '((:a . 10) (:b . 20) (:c . 30)) 1)
(-> '((:a . 10) (:b . 20) (:c . 30)) :b)
;; (-> '((:a . 10) (:b . 20) (:c . 30)) 'cdr 'cdr 'car) ; not yet
;; (-> '(:a 10 :b 20 :c 30) 'cdr 'cdr 'car) ; not yet
(-> s 'f 0 's-h 'y 2)
(-> s 'f 1 's-l 1)
(-> s 'f 0 's-l :b '1+ (function sin))
(-> s 'f 0 's-a 1)
;;(-> s 'f 0 's-a 1 (lambda (v) (coerce v 'list))) ; not yet
(-> stream 'read 'string-downcase)
(-> stream 'read 'string-upcase)
)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
Ulrich Hobelmann
In case nobody has yet suggested Practical Common Lisp to you, let me do
it. It has a whole chapter on LOOP, too, and IMHO not at all hard to
understand.
verec
> verec wrote:
>> On 2006-01-14 15:47:18 +0000, Ulrich Hobelmann <u.hob...@web.de> said:
>>
>>> Inside a LOOP lists and arrays are pretty much the same to loop over...
>>
>> Thanks. But I'm not ready for "loop" yet! I must admit of
>> the charm of the "collect" form, but that's for ... phase 4! :-)
>
> In case nobody has yet suggested Practical Common Lisp to you, let me
> do it. It has a whole chapter on LOOP, too, and IMHO not at all hard
> to understand.
I know of Peter Seibel's talent, and PCL is a most excellent
book. That said, even his chapter cannot overcome what Paul
Graham says in ANSI CL, page 239-240:
"If you are one of the many Lisp programmers who have been
planning, one day, do understand what loop does, there is
some good news and some bad news. The good news is that
you are not alone: almost no one understands it. The bad
news is that you probably never will, because the ANSI
standard does not really give a formal specification of
its behavior".
I've still got way too many holes in my uunderstanding
of Common Lisp for loop to make it to the top of my list,..
--
JFB
Edi Weitz
> I know of Peter Seibel's talent, and PCL is a most excellent
> book. That said, even his chapter cannot overcome what Paul Graham
> says
Why? Is Paul Graham God?
> [Graham:] The bad news is that you probably never will, because the
> ANSI standard does not really give a formal specification of its
> behavior.
That hasn't hindered Lisp vendors to include LOOP with their
implementations and it hasn't hindered lots of Lisp hackers to use
LOOP successfully. Are they all wrong?
There are other places where the ANSI spec isn't 100% formally
correct. That doesn't make it useless. I'm sure the same can be said
about the specifications of other programming languages.
Paul Graham might be a fine writer but idiosyncrasies are just that -
idiosyncrasies.
Cheers,
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq "spam...@agharta.de" 5) "edi")
verec
> On Sun, 15 Jan 2006 22:02:20 +0000, verec <ve...@mac.com> wrote:
>
>> I know of Peter Seibel's talent, and PCL is a most excellent
>> book. That said, even his chapter cannot overcome what Paul Graham
>> says
>
> Why? Is Paul Graham God?
If you have to ask, then he surely is! :-)
>> [Graham:] The bad news is that you probably never will, because the
>> ANSI standard does not really give a formal specification of its
>> behavior.
>
> That hasn't hindered Lisp vendors to include LOOP with their
> implementations and it hasn't hindered lots of Lisp hackers to use
> LOOP successfully.
Who said any vendors has been hindered?
> Are they all wrong?
Nobody understand Quatum Mechanics, yet it has been applied
by physicists day in and day out for almost a whole century...
I am not saying that lisp vendors do not understand it, I
am saying that *I* don't. But even the fact of mentionning
loop in _this_ thread is a bit off topic.
> There are other places where the ANSI spec isn't 100% formally
> correct. That doesn't make it useless. I'm sure the same can be said
> about the specifications of other programming languages.
>
> Paul Graham might be a fine writer but idiosyncrasies are just that -
> idiosyncrasies.
Do you have a problem if I set my priorities different
to yours, and spend a few of my aging brain cells to other
lispy topics of interest (such as deciphering Pascal Bourguigon
's -> operator, which, even without loop is a serious
headache for me :-) ?
--
JFB
Ulrich Hobelmann
> "If you are one of the many Lisp programmers who have been
> planning, one day, do understand what loop does, there is
> some good news and some bad news. The good news is that
> you are not alone: almost no one understands it. The bad
> news is that you probably never will, because the ANSI
> standard does not really give a formal specification of
> its behavior".
>
> I've still got way too many holes in my uunderstanding
> of Common Lisp for loop to make it to the top of my list,..
If you shouldn't like loop at all for some reason, there's a package
called ITERATE, I think, that does similar things.
Kenny Tilton
> I've still got way too many holes in my uunderstanding
> of Common Lisp for loop to make it to the top of my list,..
Your mileage is fine, but a friendly tip to other lurking newbies: learn
loop before writing any serious code. It took me nine years before PCL
came along and presented the beast manageably enough (for this poor
reader), and now I use it for everything (which helps given its
hairieness <g>).
kenny
Christopher Browne
> the idea that Lisp's lists are both necessary and not
> the only game in town.
>
> This is from the perspective of a newbie (myself) who
> went through the successive learning phases of:
>
> 1 lists are complicated and daunting. And who needs
> a cons anyway?
I think there's a lot of truth to this one. The "trouble" with lists
in Lisp that is exposed here is that intro courses tend to pretend
that lists are the only data structure that Lisp has available.
Furthermore, it is *way* common for beginners' code to consist of
mind-bendingly painful and inscrutable blocks of CAR/CDR combinations.
This is all quite common, and intrinsic to the way people first
experience the "base features" of the language
- In FORTH, the same sort of thing tends to happen with stack
manipulations. Beginners wind up doing way too many DUP/SWAP/ROLL
operations, whereas "experts" wind up writing code that doesn't
need to manipulate the stack terribly much
- In Pascal, the "big pain" winds up being that you have horrible
sets of nested procedures where parameter names got horribly
overloaded because you just kept nesting and nesting...
These days, I periodically "grep" my source tree for CAR/CDR, and see
to getting rid of them :-).
> 2 lists are the skeleton upon which the entire Lisp
> language/engine is built. Whenever you (defun or
> (defmacro you're just creating some kind of list.
> Your source code is a long suite of lists.
Quite right. This is the point at which the importance of lists
emerges...
> 3 for all their merit, lists are not appropriate for
> every single kind of use. Other data structures
> exist that are most always a better map to the
> problem at hand, be it hash-table, arrays, strings,
> structure or even classes...
>
> Here am I, in this stage 3: lists for all the code
> itself, lists for data sometimes, anything other than
> list when appropriate.
I'm tending towards simple use of classes for most things. A class
is, at base, generally a bit preferable to a DEFSTRUCT, and lets you
hide the details as to what data structure you're using.
> Lists are a good match for recursion, and thus for "functional
> programming" because lists can contain lists. But so do arrays
> (which can contain other arrays, up to at least ARRAY-RANK-LIMIT
> levels of nesting) hash-tables, which can contain other hash-tables
> or even instances of classes that can go to any arbitray level of
> nesting.
It's easy to define a DEFSTRUCT suitable for defining a binary tree
(or a B-tree, for that matter); that will typically be handled in a
recursive manner too.
> So, being a "good match" for recursive algorithms is
> not an attribute unique to lists, though the splitting
> of lists along the lines of "first-item-of" and "rest-of"
> (car and cdr) certainly makes the coding far easier than
> doing the same for arrays, hash-table, etc...
A way that may be useful to think about this is that Common Lisp
includes a whole lot of functions that are intended to act on
"sequences," which are the generalization of arrays/vectors/lists.
> But then, as much as lists don't scale too well as hash-tables,
> arrays seem quite overkill and inefficient when linked lists are
> just right.
Well, if you hide the collector in a defclass definition, then most of
your program may be able to ignore what data structure is being used
to implement "collections" of data.
Not all of your program needs to know how you are aggregating
collections of things together; the *less* pervasive that knowledge
is, the easier it may be for you to change data structures when you
discover that you need to "do better."
Lists tend to be a quick and easy place to start; if they turn out to
be a bottleneck, that is the time to pick something carefully.
And if you have 15 places where you are "collecting" things, you may
discover that in 13 of those places, lists are perfectly fine, and
that there are only two cases where something cleverer needs to be done.
--
let name="cbbrowne" and tld="gmail.com" in name ^ "@" ^ tld;;
http://cbbrowne.com/info/slony.html
All ITS machines now have hardware for a new machine instruction --
XOI Execute Operator Immediate.
Please update your programs.
John Thingstad
>
> Do you have a problem if I set my priorities different
> to yours, and spend a few of my aging brain cells to other
> lispy topics of interest (such as deciphering Pascal Bourguigon
> 's -> operator, which, even without loop is a serious
> headache for me :-) ?
Well it is a function with name '->' not a operator.
http://www.lispworks.com/documentation/HyperSpec/Body/02_cd.htm
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Pascal Bourguignon
> These days, I periodically "grep" my source tree for CAR/CDR, and see
> to getting rid of them :-).
A nice trick to avoid excessive use of CAR/CDR is to use defstruct
with :type list:
(defstruct (node (:type list))
label color left right)
Then you can easily write literal data:
(defparameter *tree*
'("root" :blue
("child-1" :violet nil nil)
("child-2" :green
("child-21" :yellow nil nil)
("child-22" :black nil nil))))
and use structure functions to access the lists:
(node-label *tree*) -> "root"
(node-color (node-left *tree*)) -> :VIOLET
(node-label (node-left (node-right *tree*))) -> "child-21"
(setf (node-left (node-left *tree*)) (make-node :label "child-11" :color :red))
-> ("child-11" :RED NIL NIL)
*tree*
-> ("root" :BLUE ("child-1" :VIOLET ("child-11" :RED NIL NIL) NIL)
("child-2" :GREEN ("child-21" :YELLOW NIL NIL) ("child-22" :BLACK NIL NIL)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
ADVISORY: There is an extremely small but nonzero chance that,
through a process known as "tunneling," this product may
spontaneously disappear from its present location and reappear at
any random place in the universe, including your neighbor's
domicile. The manufacturer will not be responsible for any damages
or inconveniences that may result.
verec
> A nice trick to avoid excessive use of CAR/CDR is to use defstruct
> with :type list:
>
> (defstruct (node (:type list))
> label color left right)
[...]
> (defparameter *tree*
> '("root" :blue ("child-1" :violet nil nil)
> ("child-2" :green ("child-21" :yellow nil nil)
> ("child-22" :black nil nil))))
Does this imply:
(eq (node-left *tree*) (nth 2 *tree*)) => T ???
But then:
(listp *tree*) => ???
(node-p *tree*) => ???
--
JFB
Pascal Bourguignon
> On 2006-01-16 00:40:16 +0000, Pascal Bourguignon <sp...@mouse-potato.com> said:
>
>> A nice trick to avoid excessive use of CAR/CDR is to use defstruct
>> with :type list:
>> (defstruct (node (:type list))
>> label color left right)
> [...]
>> (defparameter *tree*
>> '("root" :blue ("child-1" :violet nil nil)
>> ("child-2" :green ("child-21" :yellow nil nil)
>> ("child-22" :black nil nil))))
>
> Does this imply:
>
> (eq (node-left *tree*) (nth 2 *tree*)) => T ???
Let's ask it:
(fdefinition 'node-left)
->
#<FUNCTION NODE-LEFT (SYSTEM::OBJECT) (DECLARE (SYSTEM::IN-DEFUN NODE-LEFT))
(BLOCK NODE-LEFT (THE T (NTH 2 SYSTEM::OBJECT)))>
> But then:
>
> (listp *tree*) => ???
> (node-p *tree*) => ???
Indeed *tree* is a list, and a cons.
(values (listp *tree*) (consp *tree*)) -> T ; T
defstruct with :type list doesn't produce the predicate node-p. If
you need it, you must add a discriminant and implement it yourself;
for example:
(defstruct (node (:type list) (:constructor %make-node))
type label color left right)
(let ((type (gensym "NODE")))
(defun make-node (&key label color left right)
(%make-node :type type :label label :color color :left left :right right))
(defun node-p (object)
(and (consp object) (eq type (car object)))))
But if you need such a typed structure, you should use normal
structures instead.
The point of defstruct :type list, is that it allow you to "pun", like
with cons and list:
(subst :magenta :violet *tree*)
->
("root" :BLUE ("child-1" :MAGENTA ("child-11" :RED NIL NIL) NIL)
("child-2" :GREEN ("child-21" :YELLOW NIL NIL) ("child-22" :BLACK NIL NIL)))
This is particularly handy for quick-and-dirty prototype. Often, for
production code, you'll be wanting to greenspun, that is, to
reimplement the functions that already exist in Common Lisp, just to
apply them to your own ADT. Some call that "good practices"... Well,
it depends if what you need to implement is already done in CL or not.
--
__Pascal Bourguignon__ http://www.informatimago.com/
CONSUMER NOTICE: Because of the "uncertainty principle," it is
impossible for the consumer to simultaneously know both the precise
location and velocity of this product.
Frédéric Jolliton
>>> A nice trick to avoid excessive use of CAR/CDR is to use defstruct
>>> with :type list:
>>> (defstruct (node (:type list))
>>> label color left right)
[...]
> defstruct with :type list doesn't produce the predicate node-p. If
> you need it, you must add a discriminant and implement it yourself;
> for example:
[...]
You can also use :named option:
> (defstruct (node (:type list) :named)
label color left right)
NODE
> (make-node)
(NODE NIL NIL NIL NIL)
> (node-p *)
T
> (fdefinition 'node-p)
#<FUNCTION NODE-P (SYSTEM::OBJECT) (DECLARE (SYSTEM::IN-DEFUN NODE-P))
(BLOCK NODE-P
(AND (SYSTEM::CONSES-P 5 SYSTEM::OBJECT)
(EQ (NTH 0 SYSTEM::OBJECT) 'NODE)))>
--
Frédéric Jolliton