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))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
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.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Wed, 22 Nov 2006 09:45:32 +0100, Rob Warnock <····@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.
>
> (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.
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
Thanks. That looks more like what I was looking for.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
John Thingstad <··············@chello.no> wrote:
+---------------
| Rob Warnock <····@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.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
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))
In Scheme I would write
(define (depth a)
(cond ((pair? a)
(+ 1 (apply max (map depth a))))
(else 0)))
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
Nils M Holm wrote:
> 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))
>
> In Scheme I would write
>
> (define (depth a)
> (cond ((pair? a)
> (+ 1 (apply max (map depth a))))
> (else 0)))
We can do about the same thing in Lisp:
(defun depth (tree)
(if (consp tree)
(1+ (apply #'max (mapcar #'depth tree)))
0))
And then we can also do it in a readable way:
(defun depth (tree)
(if (atom tree)
0
(loop for node in tree
maximizing (depth node) into depth
finally (return (1+ depth)))))
+ "Kaz Kylheku" <········@gmail.com>:
| And then we can also do it in a readable way:
|
| (defun depth (tree)
| (if (atom tree)
| 0
| (loop for node in tree
| maximizing (depth node) into depth
| finally (return (1+ depth)))))
Nice. But I think I can improve even on this:
(defun depth (tree)
(if (atom tree)
0
(1+ (loop for node in tree
maximizing (depth node)))))
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell
Am 22.11.2006 17:41 Uhr schrieb "Harald Hanche-Olsen" unter
<······@math.ntnu.no> in ···············@shuttle.math.ntnu.no:
> + "Kaz Kylheku" <········@gmail.com>:
>
> | And then we can also do it in a readable way:
> |
> | (defun depth (tree)
> | (if (atom tree)
> | 0
> | (loop for node in tree
> | maximizing (depth node) into depth
> | finally (return (1+ depth)))))
>
> Nice. But I think I can improve even on this:
>
> (defun depth (tree)
> (if (atom tree)
> 0
> (1+ (loop for node in tree
> maximizing (depth node)))))
CL-USER 1 > (defun depth (tree)
(if (atom tree)
0
(1+ (loop for node in tree
maximizing (depth node)))))
DEPTH
CL-USER 2 > (let ((n1 '(1))) (loop repeat 1000 do (setf n1 (list n1)))
(depth n1))
Stack overflow (stack size 16000).
...
On Wed, 22 Nov 2006 09:18:19 +0100, Nils M Holm
<·················@online.de> wrote:
> (define (depth a)
> (cond ((pair? a)
> (+ 1 (apply max (map depth a))))
> (else 0)))
Thanks! Translating gives:
(defun depth (tree)
(if (consp tree)
(1+ (apply #'max (mapcar #'depth tree)))
0))
But due to a argumant limit of 255 I don't this works in the general case
so I use:
(defun depth (tree)
(if (consp tree)
(1+ (loop for item in (mapcar #'depth tree) maximizing item))
0))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
John Thingstad <··············@chello.no> wrote:
+---------------
| Nils M Holm <·················@online.de> wrote:
| > (define (depth a)
| > (cond ((pair? a)
| > (+ 1 (apply max (map depth a))))
| > (else 0)))
|
| Thanks! Translating gives:
|
| (defun depth (tree)
| (if (consp tree)
| (1+ (apply #'max (mapcar #'depth tree)))
| 0))
|
| But due to a argumant limit of 255 I don't this works in the general case...
+---------------
So use REDUCE instead of APPLY:
(1+ (reduce #'max (mapcar #'depth tree)))
+---------------
| so I use:
| (defun depth (tree)
| (if (consp tree)
| (1+ (loop for item in (mapcar #'depth tree) maximizing item))
| 0))
+---------------
Works, but it's less "functional"... ;-} ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Wed, 22 Nov 2006 10:01:18 +0100,
"John Thingstad" <··············@chello.no> wrote:
> On Wed, 22 Nov 2006 09:18:19 +0100, Nils M Holm
> <·················@online.de> wrote:
>> (define (depth a)
>> (cond ((pair? a)
>> (+ 1 (apply max (map depth a))))
>> (else 0)))
>
> Thanks! Translating gives:
>
> (defun depth (tree)
> (if (consp tree)
> (1+ (apply #'max (mapcar #'depth tree)))
> 0))
>
> But due to a argumant limit of 255 I don't this works in the general
> case so I use:
I am not sure there is a limit of 255. Why do you think there is one?
CL-USER> (apply #'max
(loop for x below 300
collect x))
299
CL-USER>
Even with a recursive version of #'tree-depth which descends into more
than 255 levels, there is no problem here (SBCL on FreeBSD):
CL-USER> (defun tree-depth (tree)
(cond ((not (consp tree)) 0)
(t (apply #'max
(mapcar (lambda (x) (+ 1 (tree-depth x))) tree)))))
TREE-DEPTH
CL-USER> (tree-depth
(loop with result = nil
for item below 300
do (setf result (list item result))
finally (return result)))
300
CL-USER>
Giorgos Keramidas <········@ceid.upatras.gr> wrote:
> On Wed, 22 Nov 2006 10:01:18 +0100,
> "John Thingstad" <··············@chello.no> wrote:
>> (defun depth (tree)
>> (if (consp tree)
>> (1+ (apply #'max (mapcar #'depth tree)))
>> 0))
>>
>> But due to a argumant limit of 255 I don't this works in the general
>> case so I use:
>
> I am not sure there is a limit of 255. Why do you think there is one?
I'm not sure where 255 is coming from. The actual limit that a
portable program can depend on is 50 (see CALL-ARGUMENTS-LIMIT).
--
Juho Snellman
On 24 Nov 2006 15:53:58 GMT, Juho Snellman <······@iki.fi> wrote:
>Giorgos Keramidas <········@ceid.upatras.gr> wrote:
>>On Wed, 22 Nov 2006 10:01:18 +0100,
>>"John Thingstad" <··············@chello.no> wrote:
>>> (defun depth (tree)
>>> (if (consp tree)
>>> (1+ (apply #'max (mapcar #'depth tree)))
>>> 0))
>>>
>>> But due to a argumant limit of 255 I don't this works in the general
>>> case so I use:
>>
>> I am not sure there is a limit of 255. Why do you think there is one?
>
> I'm not sure where 255 is coming from. The actual limit that a
> portable program can depend on is 50 (see CALL-ARGUMENTS-LIMIT).
Ah! Much obliged, thanks :-)
Apparently, SBCL sets this much much higher, so I wouldn't have noticed
that something is unportable, even if I tried thousands of arguments:
CL-USER> (describe 'CALL-ARGUMENTS-LIMIT)
CALL-ARGUMENTS-LIMIT is an external symbol in #<PACKAGE "COMMON-LISP">.
It is a constant; its value is 536870911.
Constant documentation:
The exclusive upper bound on the number of arguments which may be passed
to a function, including &REST args.
; No value
CL-USER> (format t "~A ~A"
(lisp-implementation-type)
(lisp-implementation-version))
SBCL 0.9.18
NIL
CL-USER>
This led me to http://wiki.alu.org/Lisp_Gotchas which was very
informative about other common problems Lisp programs may face,
Thank you again
Giorgos Keramidas <········@ceid.upatras.gr> writes:
> I am not sure there is a limit of 255. Why do you think there is one?
It's implementation-dependent. See CALL-ARGUMENTS-LIMIT.
On Wed, 22 Nov 2006 07:22:26 +0100, 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))
>
Ok, summing up the best contedenders are:
(defun tree-depth (tree)
(cond
((null tree) 0)
((consp tree)
(1+ (reduce #'max (mapcar #'depth tree))))
(t 1)))
(defun tree-depth (tree)
(cond
((null tree) 0)
((consp tree)
(1+ (loop for node in tree maximizing (depth node))))
(t 1)))
The first is succinct the second is slightly more efficient.
(defparameter tree '(1 2 (3 (4) 5) (6 (7 (8 9 (10)))) 11 12))
(tree-node nil) -> 0
(tree-node 17) -> 1
(tree-node '(17) -> 1
(tree-node tree) -> 5
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
John Thingstad <··············@chello.no> wrote:
> (defun tree-depth (tree)
> (cond
> ((null tree) 0)
> ((consp tree)
> (1+ (reduce #'max (mapcar #'depth tree))))
> (t 1)))
Using REDUCE instead of APPLY is indeed a good idea.
I did not think about implementation limits when
writing my version.
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
On Wed, 22 Nov 2006 11:15:25 +0100, John Thingstad
<··············@chello.no> wrote:
correction.
in the first
(1+ (reduce #'max (mapcar #'tree-depth tree))))
and the second
(1+ (loop for node in tree maximizing (tree-depth node))))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> (defparameter tree '(1 2 (3 (4) 5) (6 (7 (8 9 (10)))) 11 12))
This s-exp is not _a_ tree. It can represent tens of different trees!
See: http://groups.google.com/group/comp.lang.lisp/msg/b8d9376744b4ebb1
--
__Pascal Bourguignon__ http://www.informatimago.com/
HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.
On 2006-11-22 05:15:25 -0500, "John Thingstad" <··············@chello.no> said:
> Ok, summing up the best contedenders are:
just for completeness:
(defmethod generic-tree-depth ((tree t)) (if (null tree) 0 1))
(defmethod generic-tree-depth ((tree cons))
(1+ (loop for node in tree maximizing (generic-tree-depth node))))
On 2006-11-22 13:18:02 -0500, Raffael Cavallaro
<················@pas-d'espam-s'il-vous-plait-mac.com> said:
> just for completeness:
>
> (defmethod generic-tree-depth ((tree t)) (if (null tree) 0 1))
> (defmethod generic-tree-depth ((tree cons))
> (1+ (loop for node in tree maximizing (generic-tree-depth node))))
or even:
(defmethod generic-tree-depth ((tree (eql nil))) 0)
(defmethod generic-tree-depth ((tree t)) 1)
(defmethod generic-tree-depth ((tree cons))
(1+ (loop for node in tree maximizing (generic-tree-depth node))))
though this latter is a bit longer.
On 2006-11-22 14:18:11 -0500, Pascal Bourguignon <···@informatimago.com> said:
> (defgeneric gtd (tree)
> (:method ((tree null)) 0)
> (:method ((tree t)) 1)
> (:method ((tree cons)) (max (1+ (gtd (car tree))) (gtd (cdr tree)))))
>
> (gtd (loop repeat 10000 for tr = (list t) then (list tr) finally
> (return tr)))
> --> 10001
> (gtd (loop repeat 10000 for tr = (list nil) then (list tr) finally
> (return tr)))
> --> 100000
> (gtd (loop repeat 10000 for tr = (list) then (list tr) finally
> (return tr)))
> --> 9999
CL-USER 60 > (loop repeat 3 for tr = (list t) then (list tr) finally
(return tr))
(((T)))
CL-USER 61 > (loop repeat 3 for tr = (list) then (list tr) finally
(return tr))
(((NIL)))
CL-USER 62 > (loop repeat 3 for tr = (list) then (list tr) finally
(return tr))
((NIL))
These three things don't return the same tree/list structure (they are
not equal under tree-equal even though they all have the same length of
1 and the last two have nil as their sole element), so why should they
return the same tree-depth?
By convention of this function, a node that is nil has a 0 depth, a
node that is t has a depth of 1, and any cons node has the depth of its
deepest included node. I'm not really seeing what the problem is.
CL-USER 67 > (generic-tree-depth '(t))
2
CL-USER 68 > (generic-tree-depth t)
1
CL-USER 69 > (generic-tree-depth nil)
0
Are you perhaps confused by the fact that trees of equal length with
the same lone element are not necessarily tree-equal?
CL-USER 78 > (length (loop repeat 3 for tr = (list nil) then (list
tr) finally (return tr)))
1
CL-USER 79 > (length (loop repeat 3 for tr = (list) then (list tr)
finally (return tr)))
1
CL-USER 80 > (tree-equal (loop repeat 3 for tr = (list nil) then
(list tr) finally (return tr))
(loop repeat 3 for tr = (list) then (list
tr) finally (return tr)))
NIL
On 2006-11-22 15:57:58 -0500, Raffael Cavallaro
<················@pas-d'espam-s'il-vous-plait-mac.com> said:
> On 2006-11-22 14:18:11 -0500, Pascal Bourguignon <···@informatimago.com> said:
>
>> (defgeneric gtd (tree)
>> (:method ((tree null)) 0)
>> (:method ((tree t)) 1)
>> (:method ((tree cons)) (max (1+ (gtd (car tree))) (gtd (cdr tree)))))
>>
>> (gtd (loop repeat 10000 for tr = (list t) then (list tr) finally
>> (return tr)))
>> --> 10001
>> (gtd (loop repeat 10000 for tr = (list nil) then (list tr) finally
>> (return tr)))
>> --> 100000
>> (gtd (loop repeat 10000 for tr = (list) then (list tr) finally
>> (return tr)))
>> --> 9999
>
> CL-USER 60 > (loop repeat 3 for tr = (list t) then (list tr) finally
> (return tr))
> (((T)))
>
> CL-USER 61 > (loop repeat 3 for tr = (list) then (list tr) finally
> (return tr))
> (((NIL)))
>
> CL-USER 62 > (loop repeat 3 for tr = (list) then (list tr) finally
> (return tr))
> ((NIL))
>
> These three things don't return the same tree/list structure (they are
> not equal under tree-equal even though they all have the same length of
> 1 and the last two have nil as their sole element), so why should they
> return the same tree-depth?
Or is this just another version Pascal, not a critique as I originally thought?
Raffael Cavallaro <················@pas-d'espam-s'il-vous-plait-mac.com> writes:
> On 2006-11-22 15:57:58 -0500, Raffael Cavallaro
> <················@pas-d'espam-s'il-vous-plait-mac.com> said:
>
>> On 2006-11-22 14:18:11 -0500, Pascal Bourguignon <···@informatimago.com> said:
>>
>>> (defgeneric gtd (tree)
>>> (:method ((tree null)) 0)
>>> (:method ((tree t)) 1)
>>> (:method ((tree cons)) (max (1+ (gtd (car tree))) (gtd (cdr tree)))))
>>> (gtd (loop repeat 10000 for tr = (list t) then (list tr) finally
>>> (return tr)))
>>> --> 10001
>>> (gtd (loop repeat 10000 for tr = (list nil) then (list tr) finally
>>> (return tr)))
>>> --> 100000
>>> (gtd (loop repeat 10000 for tr = (list) then (list tr) finally
>>> (return tr)))
>>> --> 9999
>> CL-USER 60 > (loop repeat 3 for tr = (list t) then (list tr)
>> finally (return tr))
>> (((T)))
>> CL-USER 61 > (loop repeat 3 for tr = (list) then (list tr)
>> finally (return tr))
>> (((NIL)))
>> CL-USER 62 > (loop repeat 3 for tr = (list) then (list tr)
>> finally (return tr))
>> ((NIL))
>> These three things don't return the same tree/list structure (they
>> are not equal under tree-equal even though they all have the same
>> length of 1 and the last two have nil as their sole element), so why
>> should they return the same tree-depth?
>
> Or is this just another version Pascal, not a critique as I originally thought?
Yes, it was another version, shorter with defgeneric instead of
several defmethods.
--
__Pascal Bourguignon__ http://www.informatimago.com/
This universe shipped by weight, not volume. Some expansion may have
occurred during shipment.
Raffael Cavallaro <················@pas-d'espam-s'il-vous-plait-mac.com> writes:
> On 2006-11-22 14:18:11 -0500, Pascal Bourguignon <···@informatimago.com> said:
>
>> (defgeneric gtd (tree)
>> (:method ((tree null)) 0)
>> (:method ((tree t)) 1)
>> (:method ((tree cons)) (max (1+ (gtd (car tree))) (gtd (cdr tree)))))
>> (gtd (loop repeat 10000 for tr = (list t) then (list tr) finally
>> (return tr)))
>> --> 10001
>> (gtd (loop repeat 10000 for tr = (list nil) then (list tr) finally
>> (return tr)))
>> --> 100000
>> (gtd (loop repeat 10000 for tr = (list) then (list tr) finally
>> (return tr)))
>> --> 9999
>
> CL-USER 60 > (loop repeat 3 for tr = (list t) then (list tr)
> finally (return tr))
> (((T)))
>
> CL-USER 61 > (loop repeat 3 for tr = (list) then (list tr) finally
> (return tr))
> (((NIL)))
>
> CL-USER 62 > (loop repeat 3 for tr = (list) then (list tr) finally
> (return tr))
> ((NIL))
>
> These three things don't return the same tree/list structure (they are
> not equal under tree-equal even though they all have the same length
> of 1 and the last two have nil as their sole element), so why should
> they return the same tree-depth?
> By convention of this function, a node that is nil has a 0 depth, a
> node that is t has a depth of 1, and any cons node has the depth of
> its deepest included node. I'm not really seeing what the problem is.
The surprize comes from NIL = ().
(= (generic-tree-depth '(t))
(generic-tree-depth '(a))
(generic-tree-depth '(boo)))
but:
(/= (generic-tree-depth '(t))
(generic-tree-depth '(nil)))
That's why I prefer to define clearly abstract data types for trees.
> Are you perhaps confused by the fact that trees of equal length with
> the same lone element are not necessarily tree-equal?
No.
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
On 2006-11-22 16:44:58 -0500, Pascal Bourguignon <···@informatimago.com> said:
> The surprize comes from NIL = ().
But please note that the parentheses in:
'()
are not read the same as the parentheses in:
'(t)
CL-USER 150 > (consp '(t))
T
CL-USER 151 > (consp '())
NIL
The parens in '(t) read a cons, the parens in '() do not. You are being
"surprised" by the reader algorithm's varying treatment of parens. The
notation (...) means "read a chain of conses" when there's something
between the parens, but "nothing" or "nil" - the empty list - if it is
just an empty pair of parens. (see clhs 2.4.1)
Parens with stuff in them are read as conses. A single pair of parens -
'() - the empty list - however, is *not* a cons with nothing in it. A
cons with nothing in it is '(nil) or (cons nil nil) or '(nil . nil).
After all, "nil" is english for "nothing."
By chaining a bunch of parens together it's not a bunch of nils that
make something from nothing - though one might think so because the
parens make it look as though a slew of nils is making tree structure.
It is the reader creating cons cells because wherever a left paren is
not immediately followed by a right paren, it is a notation for "read a
chain of conses." Wherever a left paren *is* immediately followed by a
right paren it is a notation for "read an empty list" and the empty
list is *not a cons*. The empty list is not even a cons with nothing in
it.
Think of a tree as a set of nested boxes where the boxes are conses. If
we nest 3 empty boxes, our nest is 3 deep. If we nest 3 empty boxes the
innermost of which contains an apple, our nest is 4 deep.
CL-USER 153 > (gtd (cons (cons (cons nil nil) nil) nil))
3
CL-USER 154 > (gtd (cons (cons (cons 'apple nil) nil) nil))
4
By the definition in the hyperspec, conses make up tree structure and
atoms make up the leaves. Any nil nodes are leaves of a tree, but there
is no requirement that these nil leaves be counted as having any depth.
These nil leaves are just there as placeholders to indicate that there
is in fact *nothing there at that leaf location in the tree structure*.
It is much more consistent with the rest of the language to consider
nil leaves to have depth 0, since:
CL-USER 157 > (length '())
0
An empty or nil leaf should have depth 0, just as an empty or nil list
has length 0.
> (/= (generic-tree-depth '(t))
> (generic-tree-depth '(nil)))
So this follows as a direct consequence of nil leaves having a depth of
0. The first, '(t), is a cons containing t - in our analogy, a box with
something in it, so a nest of depth 2. The second, '(nil) is a box with
*nothing* in it, so a nest of depth 1.
Raffael Cavallaro <················@pas-d'espam-s'il-vous-plait-mac.com> writes:
> On 2006-11-22 16:44:58 -0500, Pascal Bourguignon <···@informatimago.com> said:
>
>> The surprize comes from NIL = ().
>
> But please note that the parentheses in:
>
> '()
>
> are not read the same as the parentheses in:
>
> '(t)
> [...]
>> (/= (generic-tree-depth '(t))
>> (generic-tree-depth '(nil)))
>
> So this follows as a direct consequence of nil leaves having a depth
> of 0. The first, '(t), is a cons containing t - in our analogy, a box
> with something in it, so a nest of depth 2. The second, '(nil) is a
> box with *nothing* in it, so a nest of depth 1.
All I'm saying is that until we write:
(defun make-empty-tree () nil)
(defun make-tree (label children) children)
(defun tree-leaf-p (x) (and (atom x) (not (null x))))
(defun tree-p (x) (or (consp x) (null x)))
(defun tree-empty-p (x) (null x))
(defun tree-label (x) (values))
(defun tree-children (x) x)
and using that to write:
(defun tree-depth (tree)
(cond ((tree-empty-p tree) 0)
((tree-leaf-p tree) 1)
((tree-p tree) (1+ (reduce (function max)
(mapcar (function tree-depth)
(tree-children tree))
:initial-value 0)))))
any interpretation of (), (()) or (t) is as valid as any other.
--
__Pascal Bourguignon__ http://www.informatimago.com/
WARNING: This product warps space and time in its vicinity.
On 2006-11-22 22:28:34 -0500, Pascal Bourguignon <···@informatimago.com> said:
> any interpretation of (), (()) or (t) is as valid as any other.
And all I'm saying is that not all interpretations are consistent with
the definitions of tree structure, tree, cons, atom, nil, and the
reader algorithm in the hyperspec.
The only place nil can occur in a tree is as a leaf. If we wish to
distinguish at all between tree leaves which are something and tree
leaves which are nothing (i.e., there is nothing there at that point in
the tree structure) we must use some unique distinguished atomic value
to denote the empty leaf. nil is a unique, distinguished atomic value
which already denotes emptiness in the list context, already means
"nothing," has a built-in predicate to test for it, can be elided in
forms to be read as tree structure, and can be easily specialized on in
generic functions.
The alternative is to pick some other distinguished value - say :empty
- to represent the empty leaf. But if we do so, we cannot use the
reader to make tree structure as easily:
'(((t)))
becomes:
'(((t . :empty) . :empty) . :empty)
In other words, choosing any value other than nil to represent the
empty leaf is just fighting the language.
From the above I conclude that just as nil is the empty list in list
context, so in a tree, nil should denote the empty leaf.
Finally, an empty leaf has 0 depth in just the same way that an empty
list has 0 length.
John Thingstad schrieb:
> On Wed, 22 Nov 2006 07:22:26 +0100, John Thingstad
> <··············@chello.no> wrote:
>
>> Wrote a function to calculate tree-depth here.
Id like to throw in a tail recursive version:
(defun tree-depth-tail (tree)
(labels
((push-branches (d l k)
(if (null l)
k
(push-branches d (cdr l) (cons (cons (car l) d) k))))
(tdt (trees max-depth)
(if (null trees)
max-depth
(let ((tree (caar trees))
(tree-depth (cdar trees)))
(if (consp tree)
(tdt (push-branches (1+ tree-depth) tree (cdr trees)) max-depth)
(tdt (cdr trees) (max max-depth tree-depth)))))))
(tdt (list (cons tree 0)) 0)))
In sbcl I get a stack exhausted error for
(defun tree-depth (tree)
(if (consp tree)
(1+ (reduce #'max (mapcar #'tree-depth tree)))
0))
(defun nest (n &optional l) (if (zerop n) l (nest (1- n) (cons l nil))))
(defparameter *deep-tree* (nest 999999))
(tree-depth *deep-tree*)
But the tail recursion works just fine.
Regards,
Christian
On Wed, 22 Nov 2006 07:22:26 +0100,
"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))
I'd probably use a slightly less 'verbose' style:
CL-USER> (defun tree-depth (tree)
(cond ((not (consp tree)) 0)
(t (apply #'max (mapcar
(lambda (x) (+ 1 (tree-depth x)))
tree)))))
TREE-DEPTH
CL-USER> (mapcar #'tree-depth
'((1 2 3) ;only 1 level
(1 2 (3 4)) ;two levels
(1 (2 (3 4))) ;three levels
(1 (2 (3 (4)))))) ;four levels
(1 2 3 4)
CL-USER>
The basic idea behind this is that elements which are not cons cells do
not contribute to 'increasing' the depth of the expression tree, but all
other elements will yield a tree-depth equal to their own tree-depth
plus the parent level.
You almost *had* the same idea, since you are checking with #'consp, but
there is no need for an explicit loop which accumulates the value of
`max-depth', since #'max can do this for you already (in a way which is,
IMHO, more "Lispy" too) :-)
- Giorgos
On 2006-11-23 22:36:11 -0500, Giorgos Keramidas
<········@ceid.upatras.gr> said:
> The basic idea behind this is that elements which are not cons cells do
> not contribute to 'increasing' the depth of the expression tree, but all
> other elements will yield a tree-depth equal to their own tree-depth
> plus the parent level.
The spec defines tree structure as conses, and trees as conses *and*
their atom leaves. You are counting only conses so you are counting
only the depth of the tree structure by definition of the spec, not the
depth of the full tree.
On Fri, 24 Nov 2006 21:38:40 -0500,
Raffael Cavallaro <················@pas-d'espam-s'il-vous-plait-mac.com> wrote:
> On 2006-11-23 22:36:11 -0500, Giorgos Keramidas
> <········@ceid.upatras.gr> said:
>> The basic idea behind this is that elements which are not cons cells do
>> not contribute to 'increasing' the depth of the expression tree, but all
>> other elements will yield a tree-depth equal to their own tree-depth
>> plus the parent level.
>
> The spec defines tree structure as conses, and trees as conses *and*
> their atom leaves. You are counting only conses so you are counting only
> the depth of the tree structure by definition of the spec, not the depth
> of the full tree.
By a separate check for #'consp vs. #'atom this would be counting the
depth of the full tree, right?
(cond ((consp tree) 0)
((atom tree) 1)
(t (1+ (mapcar ...))))
Giorgos Keramidas <········@ceid.upatras.gr> writes:
> By a separate check for #'consp vs. #'atom this would be counting the
> depth of the full tree, right?
>
> (cond ((consp tree) 0)
> ((atom tree) 1)
> (t (1+ (mapcar ...))))
So (tree-depth '(((1 2 3)) 4 5)) => 0 ?
On Fri, 24 Nov 2006 23:53:11 -0500, Bill Atkins <······@rpi.edu> wrote:
> Giorgos Keramidas <········@ceid.upatras.gr> writes:
>> By a separate check for #'consp vs. #'atom this would be counting the
>> depth of the full tree, right?
>>
>> (cond ((consp tree) 0)
>> ((atom tree) 1)
>> (t (1+ (mapcar ...))))
>
> So (tree-depth '(((1 2 3)) 4 5)) => 0 ?
Right, I should stop posting after a mostly sleepless night. I meant
(null tree) => 0, of course :)
On 2006-11-24 23:35:29 -0500, Giorgos Keramidas
<········@ceid.upatras.gr> said:
> By a separate check for #'consp vs. #'atom this would be counting the
> depth of the full tree, right?
>
> (cond ((consp tree) 0)
> ((atom tree) 1)
> (t (1+ (mapcar ...))))
This whole discussion turns on the two definitions of tree in the spec.
One is a fairly specific definition of a binary tree with conses as
tree structure and atoms as leaves. This is the one I'm discussing
here, and it leaves relatively little wiggle room. For our purposes
here the only real choice left to us by this more restrictive
definition in the spec is do we want to count nil leaves as having the
same depth as non-nil leaves? I say nil leaves should not be counted
the same as non-nil leaves, or else we don't count any difference
between empty conses and conses with a datum or data in them. This
leads to this counting scheme:
tree part | depth
__________________
nil leaf 0
non-nil leaf 1
cons 1
and to the set of definitions given in this thread which run like that
given by me, Pascal and others. This is Pascal's:
(defgeneric gtd (tree)
(:method ((tree null)) 0)
(:method ((tree t)) 1)
(:method ((tree cons)) (max (1+ (gtd (car tree))) (gtd (cdr tree)))))
The other definition of a tree given in the spec is very broad so as to
allow users to implement their own tree abstractions to suit their
needs and tastes. To see an exploration of this more general definition
of a tree in the spec see Pascal's detailed post on various conventions
for encoding or representing trees:
<http://groups.google.com/group/comp.lang.lisp/msg/b8d9376744b4ebb1>