Subject: Re: tree-depth
From: (Rob Warnock)
Date: Wed, 22 Nov 2006 02:45:32 -0600
Newsgroups: comp.lang.lisp
Message-ID: <>
John Thingstad <> 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)
	((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)
	((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 Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607