Hello, I'm a student who has been interested in CL for a while.
I had to learn Scheme before I could take the APCS course last year,
so that's where it started.
For my hobby projects, I code mostly in C or Python - so I have the
bad habit of finding pythonic solutions to problems while coding in
other languages. I'd like some comment on my first bit of CL code -
for some reason I feel like I'm doing something wrong.;
(defstruct (bst)
root left right)
(defun add-node (tree node)
(cond
((null tree) (make-bst :root node))
((> node (bst-root tree)) (progn (setf (bst-right tree) (add-node
(bst-right tree) node)) tree))
(t (progn (setf (bst-left tree) (add-node (bst-left tree) node))
tree))))
thanks for the time
-vk
On Jun 28, 10:27 pm, vk <······@gmail.com> wrote:
> Hello, I'm a student who has been interested in CL for a while.
> I had to learn Scheme before I could take the APCS course last year,
> so that's where it started.
>
> For my hobby projects, I code mostly in C or Python - so I have the
> bad habit of finding pythonic solutions to problems while coding in
> other languages. I'd like some comment on my first bit of CL code -
> for some reason I feel like I'm doing something wrong.;
>
> (defstruct (bst)
> root left right)
>
> (defun add-node (tree node)
> (cond
> ((null tree) (make-bst :root node))
> ((> node (bst-root tree)) (progn (setf (bst-right tree) (add-node
> (bst-right tree) node)) tree))
> (t (progn (setf (bst-left tree) (add-node (bst-left tree) node))
> tree))))
Looks fine so far. My only comment is that you don't need the PROGN
forms; the cdr of a COND clause is an implicit PROGN (as are a number
of other contexts in CL). In case that's not clear, I mean this:
(defun add-node (tree node)
(cond ((null tree)
(make-bst :root node))
((> node (bst-root tree))
(setf (bst-right tree)
(add-node (bst-right tree) node))
tree)
(t
(setf (bst-left tree) (add-node (bst-left tree) node))
tree)))
I've also reformatted the code in the traditional style I prefer, but
that of course is a matter of taste.
-- Scott
vk <······@gmail.com> writes:
>
> (defstruct (bst)
> root left right)
>
> (defun add-node (tree node)
> (cond
> ((null tree) (make-bst :root node))
> ((> node (bst-root tree)) (progn (setf (bst-right tree) (add-node
> (bst-right tree) node)) tree))
> (t (progn (setf (bst-left tree) (add-node (bst-left tree) node))
> tree))))
I'd suggest using DEFCLASS instead of DEFSTRUCT unless you have a reason
for the latter. There's nothing _wrong_ with structures, but they're
mostly superseded by classes. Also, you get more control over what else
is created.
In this case you might not even go that far; you could just use lists of
the form (left root right).
On a stylistic note, I'm not terribly fond of the COND you have
there...it conflates two separate things: creating a new tree and adding
a node to an existing tree. I'd be tempted to use generic functions:
(defmethod add-node ((tree null) node)
(make-bst :root node))
(defmethod add-node ((tree bst) node)
(if (> node (bst-root tree))
(setf (bst-right tree) (add-node (bst-right tree) node))
(setf (bst-left tree) (add-node (bst-left tree) node)))
tree)
Also, in Lisp it's okay to spell stuff out; a good Lisp environment like
SLIME offers tab completion so you can type 'bst<TAB>' and get
'binary-search-tree.'
--
Robert Uhl <http://public.xdi.org/=ruhl>
The only difference between Cosmopolitan and Playboy is that Cosmo sells
sex from a Producer perspective and Playboy sells it from a Consumer
perspective. --seen on Slashdot
Robert Uhl wrote:
> vk <······@gmail.com> writes:
>> (defstruct (bst)
>> root left right)
>>
>> (defun add-node (tree node)
>> (cond
>> ((null tree) (make-bst :root node))
>> ((> node (bst-root tree)) (progn (setf (bst-right tree) (add-node
>> (bst-right tree) node)) tree))
>> (t (progn (setf (bst-left tree) (add-node (bst-left tree) node))
>> tree))))
>
> I'd suggest using DEFCLASS instead of DEFSTRUCT unless you have a reason
> for the latter. There's nothing _wrong_ with structures, but they're
> mostly superseded by classes. Also, you get more control over what else
> is created.
defstruct superceded by CLOS???????!!!!
The rule is to use defstruct unless you know you need defclass. In this
case, defstruct is correct.
hth, kt
On Jun 29, 12:41 pm, Kenneth Tilton <·········@gmail.com> wrote:
> Robert Uhl wrote:
> > vk <······@gmail.com> writes:
> >> (defstruct (bst)
> >> root left right)
>
> >> (defun add-node (tree node)
> >> (cond
> >> ((null tree) (make-bst :root node))
> >> ((> node (bst-root tree)) (progn (setf (bst-right tree) (add-node
> >> (bst-right tree) node)) tree))
> >> (t (progn (setf (bst-left tree) (add-node (bst-left tree) node))
> >> tree))))
>
> > I'd suggest using DEFCLASS instead of DEFSTRUCT unless you have a reason
> > for the latter. There's nothing _wrong_ with structures, but they're
> > mostly superseded by classes. Also, you get more control over what else
> > is created.
>
> defstruct superceded by CLOS???????!!!!
>
> The rule is to use defstruct unless you know you need defclass. In this
> case, defstruct is correct.
I would definitely use a struct to implement the nodes of a binary
tree, as it's very unlikely that I'll even need any subclasses, never
mind multiple inheritance etc. etc.
But even though I use structs a lot, I don't know if I quite agree
with your proposed rule. I use a standard-class unless I'm pretty
sure I don't need one. That is, if I understand what the object is
going to do and how it is going to be used, and either I know there
will be no subclasses or I'm sure I know what they're all going to be,
and I don't need multiple inheritance etc., then I will use a struct.
That happens pretty frequently, but it's not the default.
Unfortunately that's a rather complicated rule to convey to a newbie.
So I can see why some suggest just going with DEFCLASS until one has
the experience to know when a struct would be better.
-- Scott
> I would definitely use a struct to implement the nodes of a binary
> tree, as it's very unlikely that I'll even need any subclasses, never
> mind multiple inheritance etc. etc.
>
> But even though I use structs a lot, I don't know if I quite agree
> with your proposed rule. I use a standard-class unless I'm pretty
> sure I don't need one. That is, if I understand what the object is
> going to do and how it is going to be used, and either I know there
> will be no subclasses or I'm sure I know what they're all going to be,
> and I don't need multiple inheritance etc., then I will use a struct.
> That happens pretty frequently, but it's not the default.
>
> Unfortunately that's a rather complicated rule to convey to a newbie.
> So I can see why some suggest just going with DEFCLASS until one has
> the experience to know when a struct would be better.
>
> -- Scott
It seems like a complicated rule for programming newbies in general,
but I do have experience designing and implementing data structures
outside of lisp - I understand what you're saying. My own rule about
structs vs. classes is this: pick whichever would be simplest to use
in the long run. I think this would apply in Lisp as well.
Seeing as most of what I do is carefree hobby coding, I tend to use
structs to prototype ideas.. but I've encountered about as many
situations in which decomposing a problem into classes seemed smarter
than managing structs, and vice versa.
> My only comment is that you don't need the PROGN
> forms; the cdr of a COND clause is an implicit PROGN (as are a number
> of other contexts in CL).
Thank you!
ACL <··················@gmail.com> writes:
> On Jun 30, 7:10 am, Paul Donnelly <·············@sbcglobal.net> wrote:
>> ACL <··················@gmail.com> writes:
>> > the thread where people suggested programming in an 'image based'
>> > style
>>
>> What's wrong with that?
>
> Well nothing is theoretically wrong with an image based style. In fact
> I find it theoretically more appealing than a source code files based
> style, however that seems irrelevant.
>
> For a newbie coming to the language, it doesn't make sense to have him
> adopt a completely different approach to storing code, as how you
> store the code is (fairly) arbitrary.
Hey, they've already got to forget everything they know. At least this
would stop them from trying to figure out how to batch compile their
work. ;)
> I would also question whether there is really an infrastructure built
> into Common Lisp implementations (in general) for that style of
> programming.
No, I don't think there is.
When I was talking about STRUCTURE I was trying to
talk about a bigger concept.
As an example is the set of ipv4 internet addresses is
which is the set of unsigned 32-bit integers. But as humans
we are not good with number like that so we assign
them symbolic names (domain names). Now we
have a mapping between numbers and symbols.
However the system to manage the mapping
of domain names (DNS servers) needed to be organized
in a hierarchical system and the domain names
became dotted symbols. As humans we imposed
a "structure" on the internet addresses. It is
not a class.
Another example is computer programs, they have
structure. (maybe like software patterns). But
a Lisp function has structure. An entry point,
local bindings, multiple return points, handlers,
etc, etc. Again not a class.
DEFSTRUCT is just a little concretization of
the concept.
Wade