I am going to do a project for my studies.
We can use any language we want, and since the project
is some time off, I am investigating the alternatives a bit.
So my question is: is Lisp good for handling binary trees?
Thomas.
Hello!
In article <··········@nntphost.cis.strath.ac.uk>,
Thomas Stegen CES2000 <··········@hotmail.com> wrote:
>I am going to do a project for my studies.
>We can use any language we want, and since the project
>is some time off, I am investigating the alternatives a bit.
>So my question is: is Lisp good for handling binary trees?
Why not?
(defstruct binary-tree
element
child-left
child-right)
or
(defclass binary-tree ()
((element :initarg :element :accessor element)
(child-left :initarg :child-left :accessor child-left)
(child-right :initarg :child-right :accessor child-right)))
(defmethod all-elements ((tree binary-tree))
(let* ((left-c (child-left tree))
(right-c (child-right tree))
(left-elements (if left-c (all-elements left-c) nil))
(right-elements (if right-c (all-elements right-c) nil)))
(concatenate 'list left-elements (cons (element tree) right-elements))))
etc.
Kind regards,
Hannah.
Thomas Stegen CES2000 wrote:
> ... is Lisp good for handling binary trees?
Lisp *IS* a binary tree.
It's basic memory structure is a cons cell of
two pointers (car and cdr) to other cons cells.
If you want to do work in binary trees,
Lisp is the obvious choice, and perhaps
that is part of the test, to see how may
students will correctly choose Lisp.
Thanks,
Jeff Sandys
In article <·················@juno.com>, Jeff Sandys wrote:
>Thomas Stegen CES2000 wrote:
>> ... is Lisp good for handling binary trees?
>
>Lisp *IS* a binary tree.
>It's basic memory structure is a cons cell of
>two pointers (car and cdr) to other cons cells.
A cons cell holds two atoms, either of which *could* be a pointer
to another cons cell.
The cons cell is one of many data types in Lisp.
Your answer is worded in a way that reinforcing the myth that Lisp is
all about list manipulation and nothing else.
>If you want to do work in binary trees,
>Lisp is the obvious choice, and perhaps
If you want to work on binary trees whose nodes have some auxiliary
information, such as a key and a pointer to some data, then you cannot
use the cons cell as your direct representation for the tree node.
···@ashi.footprints.net (Kaz Kylheku) writes:
> In article <·················@juno.com>, Jeff Sandys wrote:
> >Thomas Stegen CES2000 wrote:
> >> ... is Lisp good for handling binary trees?
> >
> >Lisp *IS* a binary tree.
> >It's basic memory structure is a cons cell of
> >two pointers (car and cdr) to other cons cells.
>
> A cons cell holds two atoms, either of which *could* be a pointer
> to another cons cell.
Nitpicking. A cons cell is not an atom.
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
* Jeff Sandys <·······@juno.com>
| Lisp *IS* a binary tree. It's basic memory structure is a cons cell of
| two pointers (car and cdr) to other cons cells.
What utter nonsense. First, a binary tree has two pointers and at least
one value. Second, "it's" and "its" are still different. Third, there
is no particular memory structure that merits "basic" in Common Lisp.
///
--
Norway is now run by a priest from the fundamentalist Christian People's
Party, the fifth largest party representing one eighth of the electorate.
--
Carrying a Swiss Army pocket knife in Oslo, Norway, is a criminal offense.
Erik Naggum wrote:
> * Jeff Sandys <·······@juno.com>
> | Lisp *IS* a binary tree. It's basic memory structure is a
> | cons cell of two pointers (car and cdr) to other cons cells.
>
> What utter nonsense.
Erik, when you use this expression you imply to me that you believe
that the above statement is absolutely untrue.
> First, a binary tree has two pointers and at least one value.
A binary tree is a structure of nodes, each with two, and only two
branches.
Each branch connects to another node or terminates at a leaf (value).
> Second, "it's" and "its" are still different.
And perhaps the "is" should have been a "was".
> Third, there is no particular memory structure that merits "basic" in Common Lisp.
Except that the heritage of Lisp is a memory structure derived from
the IBM704 that allowed its 36bit word (node or cons cell) to be used
as two 18bit addresses that with one machine instruction of the IBM704
could use the Current Address Register (CAR, the high 18bits) or the
Current Decrement Register (CDR, the lower 18bits) to quickly load
another 36bit word (node or cons cell).
This serendipitous use of a computer architecture made Lisp possible
and gave Lisp incredible computational power. Lisp gave us the first
dynamic memory allocation and garbage collection, the first
interactive computing language and the first multi-user system.
And still this incredible power is giving Lisp its long life.
And Erik, you have challenged me to unlearn Lisp 1.5, throw
out Winston and Horn, and forget that I ever learned Scheme.
My Steele is very worn and I have studied the idioms of Norvig,
so I hope you will pardon me when, sometimes, S-expressions and
link list diagrams spring into this old man's mind in my replies
to comp.lang.lisp.
Sincerely,
Jeff Sandys
* Jeff Sandys
| Lisp *IS* a binary tree. It's basic memory structure is a cons cell of
| two pointers (car and cdr) to other cons cells.
* Erik Naggum
> What utter nonsense.
* Jeff Sandys
| Erik, when you use this expression you imply to me that you believe that
| the above statement is absolutely untrue.
When you decide to highlight "is" that way, it means that Lisp can be
nothing else and that something else cannot be Lisp. _That_ is the
utter nonsense. If someone says "all X are Y", and somebody denies this,
they are _not_ saying "no X is Y" (or "all X are not Y"), and they are
_not_ denying that "some X are Y", but some people react as if they were
entitled to say "all" because their evidence suggests "some", and hence
go nuts because they think you contradict their evidence that "some" is
true. Elementary logic is not as optional as some people think it is.
> First, a binary tree has two pointers and at least one value.
| A binary tree is a structure of nodes, each with two, and only two
| branches. Each branch connects to another node or terminates at a leaf
| (value).
You carefully avoid mentioning what other information a node must have to
be useful. Not to beat you over the head with either Knuth or Leiserson,
et al, this is what Winston & Horn has to say about binary trees:
A _binary tree_ can be defined recursively either as a leaf, or as
a node with two attached binary trees. Such a binary tree can be
represented using atoms for the leaves and three-element lists for
the nodes. The first element of each list is an atom representing
a node, and the other two elements are the subtrees attached to the
node.
Abelseon, et al, agree with this representation. This is quite different
from a simple cons cell. Usually, a binary tree also includes a parent.
> Third, there is no particular memory structure that merits "basic" in
> Common Lisp.
| Except that the heritage of Lisp [...]
"Heritage" and "basic" are not even related concepts. Why bring it up?
| And Erik, you have challenged me to unlearn Lisp 1.5, throw out Winston
| and Horn, and forget that I ever learned Scheme.
What utter nonsense. If what you got out of thse good books is that
bunch of utter nonsense, you should simply re-read them. Pull yourself
together and just accept that you were mistaken. The only useful thing
you can about having been wrong is to figure out what is right.
Defending what is clearly wrong is counter-productive. Defending
yourself because you were wrong about something is just plain stupid.
///
--
Norway is now run by a priest from the fundamentalist Christian People's
Party, the fifth largest party representing one eighth of the electorate.
--
Carrying a Swiss Army pocket knife in Oslo, Norway, is a criminal offense.
Erik Naggum wrote:
>
> * Jeff Sandys
> | Lisp *IS* a binary tree. It's basic memory structure is a cons cell of
> | two pointers (car and cdr) to other cons cells.
>
> * Erik Naggum
> > What utter nonsense.
>
> * Jeff Sandys
> | Erik, when you use this expression you imply to me that you believe that
> | the above statement is absolutely untrue.
>
> When you decide to highlight "is" that way, it means that Lisp can be
> nothing else and that something else cannot be Lisp. _That_ is the
> utter nonsense. If someone says "all X are Y", and somebody denies this,
> they are _not_ saying "no X is Y" (or "all X are not Y"), and they are
> _not_ denying that "some X are Y", but some people react as if they were
> entitled to say "all" because their evidence suggests "some", and hence
> go nuts because they think you contradict their evidence that "some" is
> true. Elementary logic is not as optional as some people think it is.
>
Clarity is the first reservation used in scrutinizing logic. We both
have used unnecessary emphasis that has interfered with clear logical
expression. You apparently assumed that *IS* meant "is only". I
expressed my clarity reservation about utter (meaning absolute) nonsense
(implying untrue), and you clarified that utter nonsense just means
"false". I will avoid unnecessary emphasis and restate my primary
assertion: Lisp is a binary tree.
>
> > First, a binary tree has two pointers and at least one value.
>
> | A binary tree is a structure of nodes, each with two, and only two
> | branches. Each branch connects to another node or terminates at a leaf
> | (value).
>
> You carefully avoid mentioning what other information a node must have to
> be useful. Not to beat you over the head with either Knuth or Leiserson,
> et al, this is what Winston & Horn has to say about binary trees:
>
> A _binary tree_ can be defined recursively either as a leaf, or as
> a node with two attached binary trees. Such a binary tree can be
> represented using atoms for the leaves and three-element lists for
> the nodes. The first element of each list is an atom representing
> a node, and the other two elements are the subtrees attached to the
> node.
>
> Abelseon, et al, agree with this representation. This is quite different
> from a simple cons cell. Usually, a binary tree also includes a parent.
>
You, too, carefully avoid mentioning what other information a node must
have to be useful. Since this seems to be the crux of your argument,
that a simple cons cell is not a binary tree node, I will attempt to
provide clarity and prove otherwise.
Since we are only interested in useful nodes one might assert,
All binary tree nodes must have two branches and other information.
I have a clarity reservation, define "other information". Using the
example from Winston & Horn that follows the definition and
representation of a binary tree you quoted, I would infer that other
information is only a unique node identifier (name). I will use "name"
in the following logical expressions to avoid any confusion between
identifier (name) and identical (equal).
[1] A binary tree is a leaf or a node with two binary trees.
(A restatement of the Winston & Horn definition)
Note that there is no mention of other information or at least one value
in his definition and that "an atom representing a node" is added for
his
specific instance of the binary tree representation. Is a unique name
for each node sufficient or is there any other information that is
necessary to make a node useful? My answer, no.
Therefore assert:
[2] A binary tree node is a unique name with two branches.
If [3] a unique name with two branches is binary tree node,
and [2],
then [4] a unique name with two branches is identical to a binary tree
node.
Assert the following two statements as facts:
[5] A simple cons cell has two branches.
[6] A simple cons cell has a unique name.
(where memory address is the usual meaning of a simple cons cell name)
If [4] and [5] and [6],
Then [7] a simple cons cell is a binary tree node.
I have a clarity reservation about "parent", please define "parent" if
it
is necessary to your argument.
>
> > Third, there is no particular memory structure that merits "basic" in
> > Common Lisp.
>
> | Except that the heritage of Lisp [...]
>
> "Heritage" and "basic" are not even related concepts. Why bring it up?
>
This statement is probably true:
There is no memory structure that merits "basic" in Common Lisp.
However there is a data structure that merits basic in all Lisps, and
the
heritage of that data structure is a particular memory structure.
>
> | And Erik, you have challenged me to unlearn Lisp 1.5, throw out Winston
> | and Horn, and forget that I ever learned Scheme.
>
> What utter nonsense. If what you got out of thse good books is that
> bunch of utter nonsense, you should simply re-read them. Pull yourself
> together and just accept that you were mistaken. The only useful thing
> you can about having been wrong is to figure out what is right.
> Defending what is clearly wrong is counter-productive. Defending
> yourself because you were wrong about something is just plain stupid.
>
I do not write here to defend myself or to defend what is clearly wrong.
I write to the comp.lang.lisp group to serve and to learn.
Since you suggested that I reread Lisp 1.5 and since it was a lecture by
the author of that book, about 30 years ago, that I became aware that
Lisp is a binary tree, I will prove that assertion listing facts from
the
_Lisp 1.5 Programmer's Manual_ and my assumptions.
Facts from Lisp 1.5, found on the first two pages below the line "LISP
differs from most programming languages in three important ways":
[8] All Lisp data are s-expressions.
(where s-expressions means symbolic expressions)
[9] All Lisp source language are s-expressions.
(where source language means programs)
[10] A s-expression is an atomic symbol or a cons of two s-expressions.
My assumption inferred from Lisp 1.5:
[11] An atomic symbol is a (binary tree) leaf,
If [7] and [11] and [4] and [1],
Then [12] a s-expression is a binary tree.
My assumption inferred from Lisp 1.5:
[13] Lisp is data or source language.
One might argue that the computer instructions that evaluates
s-expressions are part of Lisp, but those computer instructions are
unique for each computer and implementation of Lisp. Therefore I assume
that the computer instructions that evaluates s-expressions are a part
of
the computer and not a part of Lisp itself.
If [13] and [8] and [9] and [12],
Then [14] Lisp is s-expressions,
If [14] and [12]
Then [15] Lisp is a binary tree.
If you wish to argue these assumptions or asserted facts, please use
clear logical expressions to avoid further misunderstand. I believe,
with the application of logic, together we can find the truth.
Sincerely,
Jeff Sandys
* Jeff Sandys
| You apparently assumed that *IS* meant "is only".
Well, no. I consider "is" without emphasis to be an implication, with
emphasis a bi-implication.
| I expressed my clarity reservation about utter (meaning absolute)
| nonsense (implying untrue), and you clarified that utter nonsense just
| means "false".
Well, no. Nonsense means "arbitrary", which is neither false nor true.
| I will avoid unnecessary emphasis and restate my primary assertion: Lisp
| is a binary tree.
Well, it is an improvement, but this time, it is just wrong. The cons
cell fails one of the primary tests of binary trees: It holds no data.
No binary tree I have ever seen described anywhere consists of _only_ two
pointers. So my concept of a binary trees necessarily contains payload.
If yours does not, we do not share the concept of a binary tree, but
there is no Final Authority on this, so I will just argue that according
no all known sources of algorithm design, your payloadless binary tree is
an anomaly. While I might not consider "an s-expression is a binary
tree" worth contesting, I certain consider "Lisp is a binary tree" to be
very, very confused, and wrong.
| You, too, carefully avoid mentioning what other information a node must
| have to be useful.
Yes, I do, because that is immaterial. _Some_ information, but I do not
care which or what.
| [1] A binary tree is a leaf or a node with two binary trees.
| (A restatement of the Winston & Horn definition)
This is about the only step of your "logic" I concur with.
| Note that there is no mention of other information or at least one value
| in his definition and that "an atom representing a node" is added for his
| specific instance of the binary tree representation. Is a unique name
| for each node sufficient or is there any other information that is
| necessary to make a node useful? My answer, no.
The question is pretty unclear relative to that simple answer.
| I write to the comp.lang.lisp group to serve and to learn.
Very noble. :)
| One might argue that the computer instructions that evaluates
| s-expressions are part of Lisp, but those computer instructions are
| unique for each computer and implementation of Lisp.
While I do not buy your cons = binary tree thing at all, and will skip it
because it appears to be very elaborately wrong instead of simply wrong,
there is an important point here about what a program is. Does it cause
action by subjecting a static machine that otherwise does nothing to a
list of instructions, or is it static data that is accepting by a "live"
machine that acts on it?
| Therefore I assume that the computer instructions that evaluates
| s-expressions are a part of the computer and not a part of Lisp itself.
This is perhaps the most interesting leap of faith involved here. (There
is nothing inferior or invalid in "leaps of faith" as such.) You seem to
regard Lisp as data for that which causes s-expressions to be evaluated.
I consider Lisp to _be_ that which causes s-expressions to be evaluated.
| If you wish to argue these assumptions or asserted facts, please use
| clear logical expressions to avoid further misunderstand. I believe,
| with the application of logic, together we can find the truth.
There is no such thing as "the truth", but conflicting notions of what is
_true_ clearly indicate an error somewhere. With conflicting premises,
such as yours and mine, it would be meaningless to strive to arrive at a
common "truth". I think your premises are constructed to support the
notion that Lisp is a binary tree, not indpendently discovered to be true.
///
--
The past is not more important than the future, despite what your culture
has taught you. Your future observations, conclusions, and beliefs are
more important to you than those in your past ever will be. The world is
changing so fast the balance between the past and the future has shifted.
Erik Naggum wrote:
<many deletions with just a few essential remaining and reordered>
> While I might not consider "an s-expression is a binary
> tree" worth contesting, I certain consider "Lisp is a binary tree"
> to be very, very confused, and wrong.
> | [1] A binary tree is a leaf or a node with two binary trees.
> | (A restatement of the Winston & Horn definition)
>
> This is about the only step of your "logic" I concur with.
> I consider Lisp to _be_ that which causes s-expressions to be evaluated.
> There is no such thing as "the truth", but conflicting notions of what
> is _true_ clearly indicate an error somewhere.
> Does it <a Lisp program> cause action by subjecting a static machine
> that otherwise does nothing to a list of instructions, or is it static
> data that is accepting by a "live" machine that acts on it?
Erik, you apparently at least understand my arguments, thank you for the
effort. If binary tree nodes must have a value and Lisp is more than
data
and source language s-expressions then Lisp is not a binary tree.
I still don't agree with your assertions, but diversity is good,
understanding is better. Conflict can be good when both parties
understand that there must be an error in the underlying assumptions.
I don't fully understand your question so let me give an anecdote as
a response.
I build robots as a hobby and was eager to demonstrate the powers of
Lisp in a maze solving robot for a contest (about 1986). Using P-Lisp,
a Lisp interpreter written in Pascal, as a template, I wrote an
interpreter in 6809 assembler. Once the code was running properly
on the evaluation board I burnt a PROM of the Lisp interpreter code.
So all the code required to evaluate s-expressions, except for a
few bytes of RAM to store current state and to make the virtual
Lisp machine, was static. If the 6809 had a built in PROM like
many embedded processors today then the Lisp interpreter would be
a single chip "live" computer running a fixed, "static" process.
The maze was stored as a binary tree with no values at the nodes,
a nil leaf representing a maze dead end and a t representing the
finish. By trimming branches that had nil leaves the remaining
tree with the t leaf would be the solution path. The accessor and
constructor methods were responsible for properly coding the maze
branches into the s-expresson of the maze. I can see the usefulness
of adding the branch names to the nodes of the maze list, it would
have made it easier for me to read when debugging and the accessor
and constructor methods could have been more generic. But I
still believe that a value and branches *representation* of
a binary tree is not the same thing as a (true) binary tree.
With the Lisp interpreter fixed in the 32K PROM the only influence
I had on the actions of the computer was the s-expressions of
the programs and data that were put into the 32K of RAM (or about
8000 nodes of cons cells). The programs and data were in a known,
fixed state when they were transferred from the floppy disk,
through the serial port, through the Lisp reader, into the RAM
node space. But once started the maze tree was created, then
solved, then converted into a program (creating new data and
source language s-expressions) that would control the robot to
run the fastest maze solution.
Earlier in college I had struggled for 4 years trying to learn
Lisp on my own. In graduate school when I saw a video tape
lecture of Lisp 1.5, I finally understood Lisp and quickly became
very proficient. My advisor said that a certain engineering
problem couldn't be solved by computer (meaning brute force
iteration) and could only be solved by the graphical method that
he taught. I used Macsyma (my reason for learning Lisp here) and
demonstrated that a computer could symbolically rearrange equations,
take the derivative and determine the root (as his graphical method
did) and learned another lesson; refuting an advisors pet theory
can severely limit a graduate student's career.
Thanks,
Jeff Sandys
Jeff Sandys wrote:
>
>... and learned another lesson; refuting an advisors pet theory
> can severely limit a graduate student's career.
Listen up, Thomas. :) This is another one of my concerns with academia.
kenny
clinisys
In article <·················@nyc.rr.com>, Kenny Tilton wrote:
>
>
>Jeff Sandys wrote:
>>
>>... and learned another lesson; refuting an advisors pet theory
>> can severely limit a graduate student's career.
>
>Listen up, Thomas. :) This is another one of my concerns with academia.
Depends on how you do it. If you care more about your career than
credit, then you can make it seem like the advisor did all the thinking,
with only modest assistance from yourself. Present just enough information
so that the conclusion arises spontaneously.
``Tell all the Truth but tell it slant'' -- Emily Dickinson
"Jeff Sandys" <·······@juno.com> wrote in message
······················@juno.com...
> [1] A binary tree is a leaf or a node with two binary trees.
> (A restatement of the Winston & Horn definition)
>
> Note that there is no mention of other information or at least one value
> in his definition and that "an atom representing a node" is added for
> his
> specific instance of the binary tree representation. Is a unique name
> for each node sufficient or is there any other information that is
> necessary to make a node useful? My answer, no.
>
> Therefore assert:
> [2] A binary tree node is a unique name with two branches.
>
> If [3] a unique name with two branches is binary tree node,
> and [2],
> then [4] a unique name with two branches is identical to a binary tree
> node.
>
> Assert the following two statements as facts:
> [5] A simple cons cell has two branches.
> [6] A simple cons cell has a unique name.
> (where memory address is the usual meaning of a simple cons cell name)
>
> If [4] and [5] and [6],
> Then [7] a simple cons cell is a binary tree node.
>
Putting aside logic for a moment.... isn't '(a b c) a linked list? Isn't a
binary tree a different beast?
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
Coby Beck wrote:
> Putting aside logic for a moment.... isn't '(a b c) a linked list?
> Isn't a binary tree a different beast?
In dotted pair form a link list '(a b c) is '(a . (b . (c . nil)))
and this is (in my view) a binary tree.
LISP(3): '(a . (b . (c . nil)))
(A B C)
Thanks,
Jeff Sandys
Jeff Sandys <·······@juno.com> writes:
> Coby Beck wrote:
> > Putting aside logic for a moment.... isn't '(a b c) a linked list?
> > Isn't a binary tree a different beast?
>
> In dotted pair form a link list '(a b c) is '(a . (b . (c . nil)))
> and this is (in my view) a binary tree.
How about the binary tree traversal? What do you get by traversing
your "binary tree" depth-first left and depth-first right? Shouldn't
you get the same elements, but in reverse order?
I think a ((a . b) . c) would be closer to a binary tree of this same
list, but here only leaf nodes are labelled, whereas in binary tree
all nodes are labelled.
This is just my view.
--
Janis Dzerins
Eat shit -- billions of flies can't be wrong.
Is the entirety of this discussion a confusion about whether each binary
node contains a "binary" number of components?
It sounds like some people think a binary tree contains two pointers,
one to a left half and one to a right half, like a cons, with data
only at the leaves. And others think a binary tree contains three
pointers, one to a left half, one to a right half, and one to a value
at the current node, whether or not it's a leaf. That is,
* A
/ \ / \
A * vs B C
/ \ / \
B C D E
'(a . (b . c)) vs (make-node :data 'a
:left 'b
:right (make-node :data 'c
:left 'd
:right 'e))
I think the usage with data at each node is more common in the literature
I've read, but it is confusing to some people because there are three,
not two, pieces of data per node; I guess binary refers to branches out,
not pointers out...
Also, some people might represent the second one as:
(list* 'a 'b (list* 'c 'd 'e))
effectively allocating a pair of conses per node, but taking four
pointers to do it, further complicating the discussion.
Kent M Pitman <······@world.std.com> writes:
> I think the usage with data at each node is more common in the
> literature I've read, but it is confusing to some people because
> there are three, not two, pieces of data per node; I guess binary
> refers to branches out, not pointers out...
I think the proper terminology would be that each node in a binary
tree contains (or references) two (or fewer) sub-trees.
Not having some extra piece of data in the node would make the
structure mostly useless, as some information must be used to guide
the search from the root towards the sougth-after node. If that
information is located in the leaves of the node's sub-trees, the
whole point of having a (binary) tree is lost, as e.g. a binary search
would degenerate into a sequential search, if I'm not much mistaken.
--
Frode Vatvedt Fjeld
"Frode Vatvedt Fjeld" <······@acm.org> wrote in message
···················@dslab7.cs.uit.no...
> Kent M Pitman <······@world.std.com> writes:
>
> > I think the usage with data at each node is more common in the
> > literature I've read, but it is confusing to some people because
> > there are three, not two, pieces of data per node; I guess binary
> > refers to branches out, not pointers out...
>
> I think the proper terminology would be that each node in a binary
> tree contains (or references) two (or fewer) sub-trees.
>
> Not having some extra piece of data in the node would make the
> structure mostly useless, as some information must be used to guide
> the search from the root towards the sougth-after node. If that
> information is located in the leaves of the node's sub-trees, the
> whole point of having a (binary) tree is lost, as e.g. a binary search
> would degenerate into a sequential search, if I'm not much mistaken.
>
I think this sums it up very well. Regardless of how it is possible to
construct, doing it without any data at a node is as you say, rather pointless.
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
Coby Beck wrote:
> "Frode Vatvedt Fjeld" <······@acm.org> wrote in message
> > Not having some extra piece of data in the node would make the
> > structure mostly useless, as some information must be used to guide
> > the search from the root towards the sougth-after node. If that
> > information is located in the leaves of the node's sub-trees, the
> > whole point of having a (binary) tree is lost, as e.g. a binary search
> > would degenerate into a sequential search, if I'm not much mistaken.
>
> I think this sums it up very well. Regardless of how it is possible
> to construct, doing it without any data at a node is as you say,
> rather pointless.
So,
Does a cons cell have some extra piece of data?
Is a cons cell a binary tree node?
Can a binary tree with some extra piece of data in the node
be represented as a s-expression?
Is a s-expression an atomic symbol or a cons of s-expressions?
Is a s-expression a binary tree?
If a cons cell does not have some extra piece of data,
is it mostly useless or rather pointless?
Please clarify your statements with answers to these questions.
Thanks,
Jeff Sandys
Jeff Sandys <·······@juno.com> writes:
> Does a cons cell have some extra piece of data?
Long ago, in Lisp for the CDC 7600, which I think had 60 bit words, I
believe it did. 20 bits each for the CAR, CDR, and CSR (pronounced
"kisser", I'm told).
In MACLISP, the HUNK datatype could masquerade as a CONS and any hunk
bigger than a hunk2 (which meant a hunk4, hunk8, ..., up to hunk512,
I think) had a "middle" that could have extra data in it, even while
car and cdr continued to work.
But in more recent lisps, like CL, no.
Still, a cons is a powerful enough building block that one can do:
+-----------------+
| |
| +-----+-----+ |
| | | | |
| | * | *---------> data
| | | | | |
| +--|--+-----+ |
| v |
| +-----+-----+ |
| | | | |
| | * | * | |
| | | | | | |
| +--|--+--|--+ |
| | | |
+-----|-----|-----+
| |
v v
lhs rhs
So it's not fair to say that trees of conses can't be binary trees
with data. It's just that the "unit" of node-ness has to be pairs of
conses, not single conses.
Maclisp's hunks were essentially the same concept, just more compact.
A contiguous vector of halfwords, with the first pair of halfwords being
the car/cdr and the subsequent words being only accessible via cxr.
[Strangely, cxr 0 was the right half of the word (its cdr) while
cxr 1 was the left (its car). The notation for hunks was similar to
conses but had a trailing dot before the close paren. (a . b . c . d .)
for a hunk4, for example.
Jeff Sandys <·······@juno.com> writes:
> Coby Beck wrote:
> > "Frode Vatvedt Fjeld" <······@acm.org> wrote in message
> > > Not having some extra piece of data in the node would make the
> > > structure mostly useless, as some information must be used to guide
> > > the search from the root towards the sougth-after node. If that
> > > information is located in the leaves of the node's sub-trees, the
> > > whole point of having a (binary) tree is lost, as e.g. a binary search
> > > would degenerate into a sequential search, if I'm not much mistaken.
> >
> > I think this sums it up very well. Regardless of how it is possible
> > to construct, doing it without any data at a node is as you say,
> > rather pointless.
>
> So,
> Does a cons cell have some extra piece of data?
It has a CAR pointer and a CDR pointer user-exposed. What it does under the
hodd is (essentially) irrelevant.
> Is a cons cell a binary tree node?
Not in and of itself. It has two pointers, but no user-exposed place
for node data.
> Can a binary tree with some extra piece of data in the node
> be represented as a s-expression?
Yes.
(defun build-leaf (data)
data)
(defun build-node (data left right)
(cons data (cons left right)))
(setq *demo-tree*
(build-node '3 (build-node 2 (build-leaf 1) nil)
(build-leaf 4)))
> Is a s-expression an atomic symbol or a cons of s-expressions?
Yes.
> Is a s-expression a binary tree?
No, an S expression is the empty list, an atom or a list of S expressions.
> If a cons cell does not have some extra piece of data,
> is it mostly useless or rather pointless?
No.
> Please clarify your statements with answers to these questions.
I hope this helps.
//INgvar
--
"No. Most Scandiwegians use the same algorithm as you Brits.
"Ingvar is just a freak."
Stig Morten Valstad, in the Monastery
Jeff Sandys <·······@juno.com> writes:
> Does a cons cell have some extra piece of data?
A cons cell holds two values. If you assign two of them for sub-trees,
there are none left for extra pieces of data.
> Is a cons cell a binary tree node?
It's not a good candidate data-type by most measures, no.
> Can a binary tree with some extra piece of data in the node be
> represented as a s-expression?
You could chose to represent a binary tree node by two cons
cells. This would give you four slots to store values in: one is used
to link the two cons cells together, two slots hold sub-trees, leaving
one slot for extra data. Obviously there is some overhead associated
with such a strategy.
> Is a s-expression an atomic symbol or a cons of s-expressions?
Yes, this is pretty much correct.
> Is a s-expression a binary tree?
In general I'd say no, but it depends somewhat on what exactly you
mean by binary tree. I find this a strange question, why do you ask?
> If a cons cell does not have some extra piece of data, is it mostly
> useless or rather pointless?
I'd say a cons cell is mostly useless for implementing binary trees,
but cons cells certainly have good uses.
> Please clarify your statements with answers to these questions.
Maybe it would be easier if you could clarify exactly what your real
concern is.
--
Frode Vatvedt Fjeld
"Jeff Sandys" <·······@juno.com> wrote in message
······················@juno.com...
> Coby Beck wrote:
> > "Frode Vatvedt Fjeld" <······@acm.org> wrote in message
> > > Not having some extra piece of data in the node would make the
> > > structure mostly useless, as some information must be used to guide
> > > the search from the root towards the sougth-after node. If that
> > > information is located in the leaves of the node's sub-trees, the
> > > whole point of having a (binary) tree is lost, as e.g. a binary search
> > > would degenerate into a sequential search, if I'm not much mistaken.
> >
> > I think this sums it up very well. Regardless of how it is possible
> > to construct, doing it without any data at a node is as you say,
> > rather pointless.
>
> So,
> Does a cons cell have some extra piece of data?
no.
> Is a cons cell a binary tree node?
no.
> Can a binary tree with some extra piece of data in the node
> be represented as a s-expression?
yes.
> Is a s-expression an atomic symbol or a cons of s-expressions?
yes.
> Is a s-expression a binary tree?
no. But a binary tree can be implemented as one. [*]
> If a cons cell does not have some extra piece of data,
> is it mostly useless or rather pointless?
no. Perhaps you are implying "as a binary tree node"? This different question
would have a different answer.
>
> Please clarify your statements with answers to these questions.
HTH... here is a simple example of an s-exp binary tree.
[*]
(defparameter *sample-tree*
'(a (b (c (d) (e)) (f nil (g))) (h nil nil)))
(defun left-child (node) (cadr node))
(defun right-child (node) (caddr node))
(defun node-data (node) (car node))
(defun right-traversal (tree)
(when tree
(cons (node-data tree)
(append (right-traversal (right-child tree))
(right-traversal (left-child tree))))))
(defun left-traversal (tree)
(when tree
(cons (node-data tree)
(append (left-traversal (left-child tree))
(left-traversal (right-child tree))))))
Coby Beck wrote:
> Jeff Sandys wrote
> > If a cons cell does not have some extra piece of data,
> > is it mostly useless or rather pointless?
>
> no. Perhaps you are implying "as a binary tree node"?
> This different question would have a different answer.
How is a cons cell different from a binary tree node
that does not have some extra piece of data?
Thanks,
Jeff Sandys
"Jeff Sandys" <·······@juno.com> wrote in message
······················@juno.com...
> Coby Beck wrote:
> > Jeff Sandys wrote
> > > If a cons cell does not have some extra piece of data,
> > > is it mostly useless or rather pointless?
> >
> > no. Perhaps you are implying "as a binary tree node"?
> > This different question would have a different answer.
>
> How is a cons cell different from a binary tree node
> that does not have some extra piece of data?
>
Its not, but this argumemt is doomed to go in circles. You want to define a
binary tree so that it includes such a useless implementation that's fine.
It's not what I think of as a binary tree. The page you cited does not support
your view either, it is merely ambiguous. If you dig deeper do you find
anything in there showing nodes with no data? I would be surprised. As was
pointed out a few messages up the thread, this data structure you describe
would have no utility.
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
Coby Beck wrote:
> Jeff Sandys wrote
> > How is a cons cell different from a binary tree node
> > that does not have some extra piece of data?
>
> Its not, [...] this data structure you describe
> would have no utility.
So a cons cell has no utility.
If this group believes that Lisp is not a binary tree,
then so be it. I choose not to debate beliefs or
other religious dogma. Thanks to everyone who has
read and thought about my assertion, I appreciate
your efforts.
Sincerely,
Jeff Sandys
Jeff Sandys <·······@juno.com> writes:
> Coby Beck wrote:
> > Jeff Sandys wrote
> > > How is a cons cell different from a binary tree node
> > > that does not have some extra piece of data?
> >
> > Its not, [...] this data structure you describe
> > would have no utility.
>
> So a cons cell has no utility.
>
> If this group believes that Lisp is not a binary tree, then so be
> it. I choose not to debate beliefs or other religious dogma.
> Thanks to everyone who has read and thought about my assertion, I
> appreciate your efforts.
Had you claimed that Lisp _programs_ were expressed as linked lists,
then there might be something to discuss.
There would be considerable legitimate _disagreement_, seeing as how
Lisp programs often get transformed into machine language before
execution, so that once they run, there may no longer be any lists or
trees or other forcibly-Lispy data structures kicking around as part
of the program.
But your contention that Lisp itself a binary tree is what represents
some bizarre sort of "religious dogma."
--
(concatenate 'string "cbbrowne" ·@acm.org")
http://www.ntlug.org/~cbbrowne/unix.html
BIOS = Bugs Inherited from Older Systems
-- ·····@otago.ac.nz
Jeff Sandys <·······@juno.com> writes:
> So a cons cell has no utility.
You are wrong. It is this "discussion" that has no (productive) utility.
--
Frode Vatvedt Fjeld
"Jeff Sandys" <·······@juno.com> wrote in message
······················@juno.com...
> Coby Beck wrote:
> > Jeff Sandys wrote
> > > How is a cons cell different from a binary tree node
> > > that does not have some extra piece of data?
> >
[original, unsnipped text]
Its not, but this argumemt is doomed to go in circles. You want to define a
binary tree so that it includes such a useless implementation that's fine.
It's not what I think of as a binary tree. The page you cited does not support
your view either, it is merely ambiguous. If you dig deeper do you find
anything in there showing nodes with no data? I would be surprised. As was
pointed out a few messages up the thread, this data structure you describe
would have no utility.
[end]
> > Its not, [...] this data structure you describe
> > would have no utility.
>
> So a cons cell has no utility.
>
I think that was a rather unfair and manipulative snip. A binary tree is
supposed to hold data in a way that allows efficient retrieval. Without data
at a node you have no way of knowing if your goal is in the left branch or in
the right branch. My text was obviously about this and reference another
illustration of this point up the thread.
There is nothing wrong with being wrong, but engaging in such stubborness and
dishonest discussion tactics is only useful for preserving a false sense of
pride.
Good day, I won't post on this topic again so no further argument necessary.
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
> If this group believes that Lisp is not a binary tree,
> then so be it. I choose not to debate beliefs or
> other religious dogma. Thanks to everyone who has
> read and thought about my assertion, I appreciate
> your efforts.
>
(Too bad you didn't try as well.)
> Sincerely,
> Jeff Sandys
>
In article <························@typhoon.tampabay.rr.com>, Coby Beck wrote:
>
>"Jeff Sandys" <·······@juno.com> wrote in message
>······················@juno.com...
>> Coby Beck wrote:
>> > Jeff Sandys wrote
>> > > How is a cons cell different from a binary tree node
>> > > that does not have some extra piece of data?
>> >
>
>[original, unsnipped text]
>Its not, but this argumemt is doomed to go in circles. You want to define a
>binary tree so that it includes such a useless implementation that's fine.
>It's not what I think of as a binary tree. The page you cited does not support
>your view either, it is merely ambiguous. If you dig deeper do you find
>anything in there showing nodes with no data? I would be surprised. As was
>pointed out a few messages up the thread, this data structure you describe
>would have no utility.
>[end]
>
>> > Its not, [...] this data structure you describe
>> > would have no utility.
>>
>> So a cons cell has no utility.
>>
>
>I think that was a rather unfair and manipulative snip. A binary tree is
>supposed to hold data in a way that allows efficient retrieval. Without data
>at a node you have no way of knowing if your goal is in the left branch or in
>the right branch.
That's a binary *search* tree. There are other binary tress, such as
binary heaps, for instance. These still have data in the nodes, but
you do not have efficient (random access) retrieval.
There do exist container trees that have no internal data other than
pointers. (By container, I mean that their tree structure is opaque
and irrelevant to the user, and supports some optimization only).
Sparse arrays implemented as trees are one example. For example, the
indirect and doubly indirect blocks in a classic UNIX filesystem are
effectively, an n-ary tree without internal data, only pointers. A
very lobsided tree, I would add. Page directories and tables in a virtual
memory system are trees without data also, based on a similar idea,
but uniformly balanced. At each level, the position to traverse is
arithmetically deduced from the sought-after array index combined with
the uniform structure of the tree, so no key data is needed. Some of the
positions at any level can be empty, so that entire parts of the tree
can be missing, allowing the virtual memory to be sparsely populated with
pages, or the file to have regions with no assigned data blocks (holes).
I think that there is no question that cons cells are used for constructing
trees. And there is no question that these trees are binary; all that
means is that there are at most two children. Not four, not three---that
would be quaternary and ternary, respectively.
However, the thread was started by some student who was wondering whether
you could code up binary trees in Lisp. From that context, you can make
a very probable guess that he was asking about binary search trees, or
something along those lines. That guess can be confirmed or refuted
by asking for a clarification. The student was not at all well served
by an answer asserting that all of Lisp is a binary tree.
In article <························@typhoon.tampabay.rr.com>, Coby Beck wrote:
>
>"Jeff Sandys" <·······@juno.com> wrote in message
>> So a cons cell has no utility.
>>
>
>I think that was a rather unfair and manipulative snip. A binary tree is
>supposed to hold data in a way that allows efficient retrieval. Without data
>at a node you have no way of knowing if your goal is in the left branch or in
>the right branch.
That's a binary *search* tree. There are other binary tress, such as
binary heaps, for instance. These still have data in the nodes, but
you do not have efficient (random access) retrieval.
There do exist container trees that have no internal data other than
pointers. (By container, I mean that their tree structure is opaque
and irrelevant to the user, and supports some optimization only).
Sparse arrays implemented as trees are one example. For example, the
indirect and doubly indirect blocks in a classic UNIX filesystem are
effectively, an n-ary tree without internal data, only pointers. A
very lobsided tree, I would add. Page directories and tables in a virtual
memory system are trees without data also, based on a similar idea,
but uniformly balanced. At each level, the position to traverse is
arithmetically deduced from the sought-after array index combined with
the uniform structure of the tree, so no key data is needed. Some of the
positions at any level can be empty, so that entire parts of the tree
can be missing, allowing the virtual memory to be sparsely populated with
pages, or the file to have regions with no assigned data blocks (holes).
I think that there is no question that cons cells are used for constructing
trees. And there is no question that these trees are binary; all that
means is that there are at most two children. Not four, not three---that
would be quaternary and ternary, respectively.
However, the thread was started by some student who was wondering whether
you could code up binary trees in Lisp. From that context, you can make
a very probable guess that he was asking about binary search trees, or
something along those lines. That guess can be confirmed or refuted
by asking for a clarification. The student was not at all well served
by an answer asserting that all of Lisp is a binary tree.
* Jeff Sandys <·······@juno.com> wrote:
|
| How is a cons cell different from a binary tree node
| that does not have some extra piece of data?
It is not, but the structures built from cons cells are not binary
trees, since they may contain cycles, and a tree, by definition, has
no cycles. And, sexps can have cycles too.
I don't consider my argument above to be a very useful one, in this
context, because it agrees with your premise, that "Lisp is <a kind of
data structure>". I don't agree with that premise.
Boris
--
·····@uncommon-sense.net - <http://www.uncommon-sense.net/>
I went to the race track once and bet on a horse that was so good that
it took seven others to beat him!
In article <·················@juno.com>, Jeff Sandys wrote:
>Clarity is the first reservation used in scrutinizing logic. We both
>have used unnecessary emphasis that has interfered with clear logical
>expression. You apparently assumed that *IS* meant "is only". I
>expressed my clarity reservation about utter (meaning absolute) nonsense
>(implying untrue), and you clarified that utter nonsense just means
>"false". I will avoid unnecessary emphasis and restate my primary
>assertion: Lisp is a binary tree.
Funny, I thought Lisp was an abstract programming language.
What was that about clarity and scrutiny? ;)
Maybe you mean that Lisp expressions are binary trees. But not
all of them are, for instance:
#(1 2 3)
*print-readably*
Arguably, parts #(1 2 3) may exist as a list somewhere in the bowels
of the reader, but in the abstract semantics, this form specifies
a vector object, not a tree or list. The character sequence #( indicates
the dispatch of some reader macro which consumes the atoms until
the matching ) and makes a vector object; in between they might be consed
up into a list.
And, of course, at the top level, Lisp code is just a sequence of forms,
which are not connected into any kind of data structure. So even if
all the top level forms in your program are trees, then your Lisp,
as a whole, is really a forest.
By a stretch of the imagination, you can pretend that the top level is
one big list, but there are no parentheses around it to express
that it is a list; and then what of the division of Lisp programs
into multiple files?
Kaz Kylheku wrote:
> Maybe you mean that Lisp expressions are binary trees. But not
> all of them are, for instance:
>
> #(1 2 3)
>
> *print-readably*
>
> Arguably, parts #(1 2 3) may exist as a list somewhere in the bowels
> of the reader, but in the abstract semantics, this form specifies
> a vector object, not a tree or list. The character sequence #( indicates
> the dispatch of some reader macro which consumes the atoms until
> the matching ) and makes a vector object; in between they might be consed
> up into a list.
>
> And, of course, at the top level, Lisp code is just a sequence of forms,
> which are not connected into any kind of data structure. So even if
> all the top level forms in your program are trees, then your Lisp,
> as a whole, is really a forest.
>
> By a stretch of the imagination, you can pretend that the top level is
> one big list, but there are no parentheses around it to express
> that it is a list; and then what of the division of Lisp programs
> into multiple files?
A non-compiling Lisp interpreter uses two lists, the contents list
that holds every function, value and atom, and the free list as a
source of available cons cells.
Yes, modern, smarter, interpreters and compilers use different data
structures, and provide the user with different data structures, all
which can be (and are in primitive interpreters) represented as cons
cells.
Thanks,
Jeff Sandys
Jeff Sandys <·······@juno.com> writes:
> I will avoid unnecessary emphasis and restate my primary assertion:
> Lisp is a binary tree.
Which is nonsense.
A binary tree is a data structure which consists of nodes that consist
of three things:
a) Some value,
b) A link "to the left," and
b) A link "to the right."
If you claimed that Lisp expressed code in the form of a set of nested
lists, nobody would argue with that.
But you then start talking about binary trees, and some nonsense about
a CONS being a binary tree, and that just demonstrates that you're
talking nonsense.
A CONS might be used to express a binary tree.
For instance, the list:
(list a nil nil)
could be considered to be a simple binary tree, consisting of the
value A, and having no further nodes.
The only way Lisp could conceivably be "a binary tree" would be if
_all_ bits of Lisp code consisted of lists of three values, where the
final two values could contain lists of the same form.
That's not what "Lisp is," so you're just talking nonsense.
--
(reverse (concatenate 'string ····················@" "454aa"))
http://www.cbbrowne.com/info/linuxdistributions.html
"The only ``intuitive'' interface is the nipple. After that, it's all
learned." -- Bruce Ediger, ·······@teal.csn.org on X interfaces.
········@acm.org wrote:
>
> Jeff Sandys <·······@juno.com> writes:
> > I will avoid unnecessary emphasis and restate my primary
> > assertion: Lisp is a binary tree.
>
> Which is nonsense.
Do you mean arbitrary, foolish or unimportant?
> A binary tree is a data structure which consists of nodes that
> consist of three things:
> a) Some value,
> b) A link "to the left," and
> b) A link "to the right."
Neither Winston & Horn or the National Institute of
Standards and Technology agree with your assertion.
http://www.nist.gov/dads/HTML/binarytree.html
> If you claimed that Lisp expressed code in the form of a set
> of nested lists, nobody would argue with that.
The Lisp expressed code in the form of a set of nested lists
are called s-expressions.
> But you then start talking about binary trees, and some
> nonsense about a CONS being a binary tree, and that just
> demonstrates that you're talking nonsense.
>
<snip>
>
> The only way Lisp could conceivably be "a binary tree" would
> be if _all_ bits of Lisp code consisted of lists of three
> values, where the final two values could contain lists of
> the same form.
>
> That's not what "Lisp is," so you're just talking nonsense.
If you refute the first assertion in a logical chain you
have broken the whole chain, you win!
If you have reservations about the other assertions in
the logic chain such as clarity, causality, sufficiency,
necessity, or tantology, please express your reservation
and I will attempt to answer.
Sincerely,
Jeff Sandys
Jeff Sandys <·······@juno.com> writes:
> ········@acm.org wrote:
> >
> > Jeff Sandys <·······@juno.com> writes:
> > > I will avoid unnecessary emphasis and restate my primary
> > > assertion: Lisp is a binary tree.
> >
> > Which is nonsense.
> Do you mean arbitrary, foolish or unimportant?
No, I mean "the assertion is _incorrect_." Claiming it to be correct
means that you're talking foolishness.
> > A binary tree is a data structure which consists of nodes that
> > consist of three things:
> > a) Some value,
> > b) A link "to the left," and
> > b) A link "to the right."
>
> Neither Winston & Horn or the National Institute of
> Standards and Technology agree with your assertion.
> http://www.nist.gov/dads/HTML/binarytree.html
I suggest you explain in what way they _disagree_ with the description
I used.
> > If you claimed that Lisp expressed code in the form of a set
> > of nested lists, nobody would argue with that.
> The Lisp expressed code in the form of a set of nested lists are
> called s-expressions.
I don't think anybody would argue with that. Yes, Lisp code is
commonly expressed as s-expressions, which typically represent a set
of nested lists.
But that's 'a set of nested lists;' not a "binary tree." You didn't
talk about s-expressions; you talked about _binary trees._
> > But you then start talking about binary trees, and some
> > nonsense about a CONS being a binary tree, and that just
> > demonstrates that you're talking nonsense.
> >
> <snip>
> >
> > The only way Lisp could conceivably be "a binary tree" would
> > be if _all_ bits of Lisp code consisted of lists of three
> > values, where the final two values could contain lists of
> > the same form.
> >
> > That's not what "Lisp is," so you're just talking nonsense.
> If you refute the first assertion in a logical chain you have broken
> the whole chain, you win!
> If you have reservations about the other assertions in the logic
> chain such as clarity, causality, sufficiency, necessity, or
> tantology, please express your reservation and I will attempt to
> answer.
I don't really care to; by starting with a poor premise, your "logic
chain" can't go anywhere particularly useful, and there's not much
value in discussing those places.
--
(concatenate 'string "cbbrowne" ·@acm.org")
http://www.cbbrowne.com/info/sap.html
PURITAS NECESSE EST -- DON'T DO RANDOM BINDINGS.
* cbbrowne
> A binary tree is a data structure which consists of
> nodes that consist of three things:
> a) Some value,
> b) A link "to the left," and
> b) A link "to the right."
* Jeff Sandys
| Neither Winston & Horn or the National Institute of
| Standards and Technology agree with your assertion.
* cbbrowne
> I suggest you explain in what way they _disagree_
> with the description I used.
From Winston & Horn:
A _binary tree_ can be defined recursively either as
a leaf, or as a node with two attached binary trees.
There is no mention of "a) Some value".
Therefore I assert that a binary tree node only requires
two branches, and that additional data is not required.
Thanks,
Jeff Sandys
"Thomas Stegen CES2000" <··········@hotmail.com> wrote in message
···············@nntphost.cis.strath.ac.uk...
> I am going to do a project for my studies.
> We can use any language we want, and since the project
> is some time off, I am investigating the alternatives a bit.
> So my question is: is Lisp good for handling binary trees?
>
> Thomas.
>
>
From your answers I conclude that this is a good time learning Lisp
since that will help me with my project. This means I am choosing
not to use Java or C, which we have classes on. If this is an utterly
idiotic choice then give me a yell ;)
Thanks for your answers.
Thomas.
(I believe I have seen Erik Naggum over at some of the
no.it.programmering.* groups? Just wondering.)
"Thomas Stegen CES2000" <··········@hotmail.com> writes:
> From your answers I conclude that this is a good time learning Lisp
> since that will help me with my project. This means I am choosing
> not to use Java or C, which we have classes on. If this is an utterly
> idiotic choice then give me a yell ;)
No, it's a very good choice. You're almost certainly going to have to
learn C and Java at some point, but if you don't take initiative
yourself, you'll probably not learn Lisp. Therefore, it's a good
choice to take this opportunity to do a significant project in a
language that's very different from most others.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
"Thomas Stegen CES2000" <··········@hotmail.com> writes:
> "Thomas Stegen CES2000" <··········@hotmail.com> wrote in message
> ···············@nntphost.cis.strath.ac.uk...
> > I am going to do a project for my studies.
> > We can use any language we want, and since the project
> > is some time off, I am investigating the alternatives a bit.
> > So my question is: is Lisp good for handling binary trees?
> >
> > Thomas.
> >
> >
>
> From your answers I conclude that this is a good time learning Lisp
> since that will help me with my project. This means I am choosing
> not to use Java or C, which we have classes on. If this is an utterly
> idiotic choice then give me a yell ;)
>
> Thanks for your answers.
It is a brave choice. Be proud of it and be ready to stand against
the slings and wounds of adverse fortune (or however it is in the
original English).
You will have a strong parenthetical foundation where to stand firm
on. :)
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
"Thomas Stegen CES2000" <··········@hotmail.com> writes:
>
> From your answers I conclude that this is a good time learning Lisp
> since that will help me with my project. This means I am choosing
> not to use Java or C, which we have classes on. If this is an utterly
> idiotic choice then give me a yell ;)
You expect that in c.l.l? Well, you may have some years ;-) But why
should anyone tell you if it's for good or bad to learn Lisp. Look at
it work with it, judge it yourself. If you conclude it has been an
idiotic choice drop it, if you think it was a good choice use it and
than _you_ can tell, well people for me it was a very good choice.
Regards
Friedrich
In article <··········@nntphost.cis.strath.ac.uk>, "Thomas Stegen
CES2000" <··········@hotmail.com> wrote:
> I am going to do a project for my studies.
> We can use any language we want, and since the project
> is some time off, I am investigating the alternatives a bit.
> So my question is: is Lisp good for handling binary trees?
Yes.
I'd recommend that you use a node class rather than building trees from
lists.
-- Bruce
······@hushmail.com writes:
> On Thu, 22 Nov 2001 03:40:47 +1300, Bruce Hoult <·····@hoult.org> wrote:
>
> >In article <··········@nntphost.cis.strath.ac.uk>, "Thomas Stegen
> >CES2000" <··········@hotmail.com> wrote:
> >
> >> I am going to do a project for my studies.
> >> We can use any language we want, and since the project
> >> is some time off, I am investigating the alternatives a bit.
> >> So my question is: is Lisp good for handling binary trees?
> >
> >Yes.
> >
> >I'd recommend that you use a node class rather than building trees from
> >lists.
>
> Why?
Because it is better and because Lists are just One-Of-The-Many data
structures available in Common Lisp.
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
······@hushmail.com writes:
> On Thu, 22 Nov 2001 03:40:47 +1300, Bruce Hoult <·····@hoult.org> wrote:
> >In article <··········@nntphost.cis.strath.ac.uk>, "Thomas Stegen
> >CES2000" <··········@hotmail.com> wrote:
> >> I am going to do a project for my studies.
> >> We can use any language we want, and since the project
> >> is some time off, I am investigating the alternatives a bit.
> >> So my question is: is Lisp good for handling binary trees?
> >
> >Yes.
> >
> >I'd recommend that you use a node class rather than building trees from
> >lists.
> Why?
If you build trees using a class (or, for that matter, a STRUCTURE),
then accesses will involve well-defined access methods.
For instance, if you define the following:
(defstruct BT
(value) (left) (right))
You can, if you like, attach code to the LEFT and RIGHT components
that enforce the requirement that LEFT and RIGHT are either:
a) NIL, or
b) of type BT
The same would be true, albeit with different implementation details,
if you use a CLOS class.
What this buys you is a total avoidance of nagging stupid list
manipulation errors. If you used the same sort of representation, but
where the (value/left/right) "protocol" is merely implicit, then any
bit of LISP that knows how to do something to a list can mess around
with the "tree-ness" of your tree. In effect, you're always just a
CAR or CDR or SETF away from nuking the tree's structure.
Given the above structure definition, you can do:
> (BT-P SOME-OBJECT)
T
and be quite sure that SOME-OBJECT isn't just some random list, but
that it is actually a binary tree.
And supposing you break it, you're not left with some random bits of
list stuff to go through; it'll break more cleanly into things that
are still Feasibly Binary Trees.
Probably more importantly, if you use some scheme that essentially
declares a type and calls it "BINARY TREE," you'll have learned that
Lisp isn't merely about manipulating lists, which is an important
lesson.
--
(concatenate 'string "cbbrowne" ·@acm.org")
http://www.ntlug.org/~cbbrowne/lisp.html
Jumping off a cliff doesn't kill you! It's only when you hit the
ground...