if 0 {Richard Suchenwirth 2004-05-31 - How deeply nested is a list? ulis asked for a list::depth function in Internal organization of the list extension. I first checked Tcllib's ::struct::list man page, but found no such thing. So I gladly took up the little challenge, but ran into problems. Assume we can all agree with
[ldepth {a b c}] == 1
[ldepth {a {b c}}] == 2and so on. But what would ldepth a be? 1 too, because it is a one-element list? 0, because it's just an "atom" and not a list? And ldepth {}? 1, because it is a list, although with zero elements? 0, because it's an atom too? Anyway, here's what I came up with, after consulting the old faithful Winston/Horn book on LISP:}
proc ldepth list {
expr {
[llength $list] == 0? 1:
[atomar $list]? 0:
1+[max [lmap ldepth $list]]
}
}
proc atomar list {expr {[lindex $list 0] eq $list}}
proc max list {
set res [lindex $list 0]
foreach e [lrange $list 1 end] {if {$e>$res} {set res $e}}
set res
}
proc lmap {func list} {
set res {}
foreach e $list {lappend res [$func $e]}
set res
}if 0 {Here's testing:
% ldepth {a b c}
1
% ldepth a
0
% ldepth {}
1
% ldepth {a {b c}}
2
% ldepth {a b c d {e {f g} h} i}
3As Tcl's list semantics differs a bit from LISP's, I'm unsure how the two corner cases, "a" and "{}", should be defined. The elegant recursion is only possible if "a" counts as 0.
What do y'all think?
Lars H: Frankly, I don't think the question "what is the depth of this Tcl list?" makes sense in general. Tcl lists are simply too wild objects for that question. For example, what should
ldepth [list \{]be? I think you will find that the above [ldepth] returns an error.
More specifically, the above recursion attempts to answer the question "What is the maximal inside depth of this Tcl list?", which fails to make sense because there is no bound on how deeply nested a list "a" can be. In essense, since "[list a]" returns "a" it must follow that the list nesting depth of that list is infinite (which makes sense, because
eval [list lindex a] $indices
does not fail for any choice of a finite list of non-negative integers as the $indices).
The question that would make sense is "What is the depth of this tree?", where a tree is defined to be any list of positive length whose elements at indices 1 to end are also trees, because in that case there is a base case (lists of length one, which constitute leaves of the tree) for a recursive definition of depth.