Subject: Re: tree-depth
From: rpw3@rpw3.org (Rob Warnock)
Date: Wed, 22 Nov 2006 04:56:40 -0600
Newsgroups: comp.lang.lisp
Message-ID: <6dOdnZWvRpp1sfnYnZ2dnUVZ_hmdnZ2d@speakeasy.net>
John Thingstad <john.thingstad@chello.no> wrote:
+---------------
| Rob Warnock <rpw3@rpw3.org> wrote:
| 
| > Or if what you actually wanted *was* a LIST-DEPTH, then
| > this may be more to your liking:
| 
| Yes sort of. Nested list's form a tree.
+---------------

True, but... The notion of "depth" depends on whether you're viewing
the structure as a "binary tree" or a "list of lists". In the "tree"
case a single long list will add its entire length to your depth result,
whereas in the "list'o'lists" case you probably don't want the result
of "depth" to depend on the length of any list per se.

+---------------
| > Its results don't agree with your original version, but I
| > think that's because your original version claimed that
| > (TREE-DEPTH NIL) ==> 1, and also blew up if given a leaf/atom,
| > e.g., (TREE-DEPTH 17) ==> <<DEBUGGER>> [even though that's
| > a perfectly good tree] -- neither of which is what I would
| > normally expect from something called TREE-DEPTH.
| 
| Requiring the argument to be be a list didn't seem unresonable to me.
| '(17) is a tree. 17 isn't. (debatable)
| nil should indeed have returned 0
+---------------

But if you're viewing the input graph as a tree, then the natural
recursive solution views every CONS within the graph as a subtree,
and since you need already to assign a value of "depth" to the
leaves of such subtrees, e.g., 0 for NIL, 1 for atom, the cleanest
recursive solution permits a leaf *as* the initial tree. If you
don't allow that, then you have to special-case the very first
call, which is... ugly. IMHO.


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607