I'm stuck on find the depth of a tree in LISP..
Given a tree is represented as
'(A B C)
'((A B) (C D))
and so on..
where atoms are the lefts and lists are additional branches..
How do you write a simple function that returns the depth of the treee?
For example..
'(A B C) ==> 1
'((A B) (C D)) ==> 2
'((A (B)) (C D)) ==> 3
Thanks.
"Mr Cool Guy" <····@here.com> writes:
> I'm stuck on find the depth of a tree in LISP..
This is a classic problem
> How do you write a simple function that returns the depth of the treee?
Think about it this way:
the depth of a tree that's nil is 0.
the depth of a tree that has left and right branches is one more than
the maximum of the depth of the subtrees starting at those nodes.
It's a recursive definition. Try to write the code from there.
dave
Thanks David..
I finally figured it out.. here's what I did..
(defun TREE_DEPTH (inList)
(cond
((null (car inList)) 0)
((atom (car inList)) (let ( (restDepth (TREE_DEPTH (cdr inList))))
(if (> restDepth 1) restDepth 1)
)
)
('t (let ( (leftDepth (+ 1 (TREE_DEPTH (car inList)))) (rightDepth
(TREE_DEPTH (cdr inList))) )
(if (> rightDepth leftDepth) rightDepth leftDepth)
)
)
)
)
--John
David Bakhash <·····@bu.edu> wrote in message
····················@engc.bu.edu...
> "Mr Cool Guy" <····@here.com> writes:
>
> > I'm stuck on find the depth of a tree in LISP..
>
> This is a classic problem
>
> > How do you write a simple function that returns the depth of the treee?
>
> Think about it this way:
>
> the depth of a tree that's nil is 0.
>
> the depth of a tree that has left and right branches is one more than
> the maximum of the depth of the subtrees starting at those nodes.
> It's a recursive definition. Try to write the code from there.
>
> dave
"Mr Cool Guy" wrote:
> I finally figured it out.. here's what I did..
>
> (defun TREE_DEPTH (inList)
> (cond
> ((null (car inList)) 0)
> ((atom (car inList)) (let ( (restDepth (TREE_DEPTH (cdr inList))))
> (if (> restDepth 1) restDepth 1)
> )
> )
> ('t (let ( (leftDepth (+ 1 (TREE_DEPTH (car inList)))) (rightDepth
> (TREE_DEPTH (cdr inList))) )
> (if (> rightDepth leftDepth) rightDepth leftDepth)
> )
> )
> )
> )
Looks OK (apart from the problem mentioned in my first comment
below).
A few comments:
Surely the depth of '(nil a b c) should be 1, not 0?
Did you mean to write "inList" instead of "(car inList)"
in the first clause of the COND?
Common Lisp has a MAX function which would let you slim
your code down a lot.
For dealing with multi-way trees like this (as opposed
to binary trees where an internal node is a pair with
the left subtree in its CAR and the right subtree in
its CDR), it's rather painful having to break everything
down one cons cell at a time. You might like to investigate
MAPCAR and REDUCE. When you've done that, you'll understand
why the following nice idea (1) almost solves the problem
and (2) doesn't (alas) actually solve it.
(defun depth (x)
(reduce (lambda (u v) (max u (1+ (depth v)))) x :initial-value 0))
The "C-style" indentation is a bit weird. Most Lispers
prefer to put strings of closing parens together
(if foo
(let ((bar (baz (+ 93 (quux 'zog)))))
(* bar bar)))
in almost all cases, rather than aligning closing parens with
their matching openers. Obviously this is no big deal, but
your Lisp will be easier for others to read if you format
it in roughly the way they do.
--
Gareth McCaughan ················@pobox.com
sig under construction
"Mr Cool Guy" <····@here.com> writes:
> I'm stuck on find the depth of a tree in LISP..
>
You should be cool enough to do your own homework.
> How do you write a simple function that returns the depth of the treee?
>
(defun tree-depth (tree)
(cond ((atom tree) 0)
(t (1+ (apply #'max (mapcar #'tree-depth tree))))))
This simple enough for you?
--
Lieven Marchand <···@bewoner.dma.be>
If there are aliens, they play Go. -- Lasker
In article <··············@localhost.localdomain>,
Lieven Marchand <···@bewoner.dma.be> wrote:
> (defun tree-depth (tree)
> (cond ((atom tree) 0)
> (t (1+ (apply #'max (mapcar #'tree-depth tree))))))
>
> This simple enough for you?
This is dangerously nonportable. CALL-ARGUMENTS-LIMIT
can be as small as 50 in a conforming implementation
of CL. Use REDUCE or (LOOP ... MAXIMIZE ...).
Paul
·····@comm.mot.com (Paul Dietz) writes:
> In article <··············@localhost.localdomain>,
> Lieven Marchand <···@bewoner.dma.be> wrote:
>
> > (defun tree-depth (tree)
> > (cond ((atom tree) 0)
> > (t (1+ (apply #'max (mapcar #'tree-depth tree))))))
> >
> > This simple enough for you?
>
>
> This is dangerously nonportable. CALL-ARGUMENTS-LIMIT
> can be as small as 50 in a conforming implementation
> of CL. Use REDUCE or (LOOP ... MAXIMIZE ...).
is there a CL in actual use that has such a low call-arguments-limit?
(in ACL 5.0:
USER(1): call-arguments-limit
16384
)
--
(espen)
Espen Vestre <·····@*do-not-spam-me*.vestre.net> writes:
> ·····@comm.mot.com (Paul Dietz) writes:
>
> > This is dangerously nonportable. CALL-ARGUMENTS-LIMIT
> > can be as small as 50 in a conforming implementation
> > of CL. Use REDUCE or (LOOP ... MAXIMIZE ...).
>
> is there a CL in actual use that has such a low call-arguments-limit?
>
> (in ACL 5.0:
> USER(1): call-arguments-limit
> 16384
> )
I agree with the warning that Paul Dietz gives. You should always
check with your vendor to see what the limits mean, and if writing
portable code, 50 is the max that should be counted on.
That said, I want to explain the current call-arguments-limit in
Allegro CL. In reality, on all productized platforms, the value is
much higher. The current limit came from the 68k port (which is now
completely dead since my poor Sun3 just recently bit the dust:-(.
The 68k has 2-byte load/store operations, and thus the count register
can be 16 bits. Accounting for an occasional fixnum shift, the
practical limit is thus (expt 2 (- 16 2)) for such an unsigned value.
If we wanted to extend the count register's range on the 68k, it
would have to use one-word operations, which are more expensive.
The RISC ports tend to be word-oriented by design. So the count
register is a full 32-bit word, and there is very little inefficiency
for large numbers of arguments. The only slight glitch is that when
a call is being made with a large enough number of arguments, setting
the count register will require two instructions insted of one, due
to the nature of constant generation in RISC architectures. Of course,
at this point, one extra instruction is unlikely to be noticed amidst
all of those parameters, and you are much more likely to have stack-
size problems before you reach the actual call limit anyway.
So what about the x86? It should have a much smaller limit, since it
has only 1-byte operations or 4-byte operations (in 32-bit mode, which
is always the case in Allegro CL). Thus, if we wanted to be efficient,
we could think of the count register as a byte, which would thus only
give us 256 maximum, even excluding fixnum shifting (which could be
eliminated with a little care). I didn't find this limit to be
acceptable, even though it is within spec. So we use some tricks to
get the most out of the count register using byte operations, but
treating the register as a full word.
An interesting problem we had at one point (I forget which version,
though we put out a patch), was a stack-overflow problem on NT:
If an apply of enough arguments was performed, the stack would be
properly decremented, but accessed in such a way that it would jump
over NT's guard pages and look like a general fault instead of a
stack overflow (which would have automatically extended the stack, if
there was room and authorization). The linux version on x86 didn't
have this problem.
So in summary, on all currently available architectures, Allegro CL
has an actual argument call limit that will probably not be reachable
without heoric stack-extension and swap-space-addition efforts. I'll
make a note to decide what number we are willing to commit to on future
versions and cahnge it to that.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
Espen Vestre <·····@*do-not-spam-me*.vestre.net> writes:
> ·····@comm.mot.com (Paul Dietz) writes:
>
> > This is dangerously nonportable. CALL-ARGUMENTS-LIMIT
> > can be as small as 50 in a conforming implementation
> > of CL. Use REDUCE or (LOOP ... MAXIMIZE ...).
>
> is there a CL in actual use that has such a low call-arguments-limit?
>
> (in ACL 5.0:
> USER(1): call-arguments-limit
> 16384
> )
If you consider GCL 2.2.1 to be a CL in actual use (which some might
dispute ;), then it get's reasonable close to the minimum:
CLISP 1997-12-06: 4294967296
CMU CL 18: 536870911
ACL 5.0TE: 16384
LispWorks Linux PE Beta (*): 255
GCL 2.2.1: 64
ANSI CL minimum: 50
(*) Note that the tested Linux Personal Edition is still in Beta, and
might therefore not represent final release versions of LispWorks for
Linux (or for other plattforms).
Regs, Pierre.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
····@acm.org (Pierre R. Mai) writes:
> Espen Vestre <·····@*do-not-spam-me*.vestre.net> writes:
>
> > ·····@comm.mot.com (Paul Dietz) writes:
> >
> > > This is dangerously nonportable. CALL-ARGUMENTS-LIMIT
> > > can be as small as 50 in a conforming implementation
> > > of CL. Use REDUCE or (LOOP ... MAXIMIZE ...).
> >
> > is there a CL in actual use that has such a low call-arguments-limit?
> >
> > (in ACL 5.0:
> > USER(1): call-arguments-limit
> > 16384
> > )
>
> If you consider GCL 2.2.1 to be a CL in actual use (which some might
> dispute ;), then it get's reasonable close to the minimum:
>
> CLISP 1997-12-06: 4294967296
> CMU CL 18: 536870911
> ACL 5.0TE: 16384
> LispWorks Linux PE Beta (*): 255
> GCL 2.2.1: 64
> ANSI CL minimum: 50
Symbolics has a really low one. I don't remember exactly what it is,
but I think it is around 80.
At any rate, the original program that started this
CALL-ARGUMENTS-LIMIT thread was:
(defun tree-depth (tree)
(cond ((atom tree) 0)
(t (1+ (apply #'max (mapcar #'tree-depth tree))))))
As with many cases of APPLY, it can be rewritten to use REDUCE:
(defun tree-depth (tree)
(cond ((atom tree) 0)
(t (1+ (reduce #'max (mapcar #'tree-depth tree)
:initial-value 0)))))
Christopher
Espen Vestre <·····@*do-not-spam-me*.vestre.net> wrote in article
<··············@wallace.nextel.no> on 25.10.1999 10:49 Uhr:
> ·····@comm.mot.com (Paul Dietz) writes:
>
>> In article <··············@localhost.localdomain>,
>> Lieven Marchand <···@bewoner.dma.be> wrote:
>>
>>> (defun tree-depth (tree)
>>> (cond ((atom tree) 0)
>>> (t (1+ (apply #'max (mapcar #'tree-depth tree))))))
>>>
>>> This simple enough for you?
>>
>>
>> This is dangerously nonportable. CALL-ARGUMENTS-LIMIT
>> can be as small as 50 in a conforming implementation
>> of CL. Use REDUCE or (LOOP ... MAXIMIZE ...).
>
> is there a CL in actual use that has such a low call-arguments-limit?
>
> (in ACL 5.0:
> USER(1): call-arguments-limit
> 16384
> )
Welcome to Macintosh Common Lisp Version 4.2!
? call-arguments-limit
8192
Yours,
Clemens
--
Clemens Heitzinger
http://ag.or.at:8000/~clemens (Lisp related material)
* Espen Vestre wrote:
> is there a CL in actual use that has such a low call-arguments-limit?
Genera on ivory claims 50, and seems actually to be able to handle
more (91 in the case I tried, though I suspect things like GF calls
will be less). On 36xx it claims 128 but I can't test that.
--tim