Subject: Re: tree-depth
From: rpw3@rpw3.org (Rob Warnock)
Date: Wed, 22 Nov 2006 02:45:32 -0600
Newsgroups: comp.lang.lisp
Message-ID: <B5ydnfTSkJyxk_nYnZ2dnUVZ_sqdnZ2d@speakeasy.net>
John Thingstad <john.thingstad@chello.no> wrote:
+---------------
| Wrote a function to calculate tree-depth here.
| Works OK, but the style looks more like C than Lisp.
| What is a good functional way of doing this?
| (defun tree-depth (tree)
|    (let ((max-depth 1))
|      (dolist (element tree)
|        (let ((depth 1))
|          (when (consp element)
|            (incf depth (tree-depth element))
|            (when (> depth max-depth)
|              (setf max-depth depth)))))
|      max-depth))
+---------------

If you replace "tree" with "list" in the above, you might
see why the style bothers you -- it's *very* LIST-oriented
[and gets the wrong answers for trees.] But if you let
"tree" *be* a (binary) tree, then it's much simpler:

    (defun tree-depth (tree)
      (cond
	((null tree) 0)
	((consp tree) (1+ (max (tree-depth (car tree))
			       (tree-depth (cdr tree)))))
	(t 1)))

Or if what you actually wanted *was* a LIST-DEPTH, then
this may be more to your liking:

    (defun list-depth (list)
      (cond
	((null list) 0)
	((consp list)
	 (1+ (reduce #'max (mapcar #'list-depth list))))
	(t 1)))

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.


-Rob

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