Depth of a list

Richard Suchenwirth 2004-05-31: How deeply nested is a list?

Description

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}}] == 2

and 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
}

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}
3

As Tcl's list semantics differ a bit from those of Lisp. 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?

LV: I think that if this code returns a value other than an error or 0, then this case needs to be treated as a list - because then the list commands are treating it as a list.

set l {a}
puts [llength $l]

And all the tcls I know return a 1 for the second statement.

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.

LV: What does depth mean? For what purpose is this depth to be used? It seems like to me, to ensure that there is a valid agreement / contract between the code writer and the code user, a definition of the concept attempting to be modeled is needed. Looking at the code is not sufficient - as a developer, only if I understand what the purpose is for the functionality can I determine whether I can make use of the code.

Examples of how a function works is not sufficient - one needs to know the problem attempting to be solved, and the idea behind the solution, before one can really determine whether or not a particular function is reusable.

CMP: The ldepth proc can be used on a parameter value to test whether it holds multiple lists or just one.

The following solution fits all (exceptional) examples I've seen up till now:

proc ldepth {list} {
    if {! [islist $list]} {return 0}
    set flatList [flatten $list]
    if {[string equal $flatList $list]} {return 1}
    return [expr {[ldepth $flatList] + 1}]
}

Instead of finding the maximum depth of each element, it flattens the list recursively as long as this has effect. If flattening has no effect, the depth is obviously 1. Strings that are not lists are considered atoms, as defined above by RS, with depth 0. The islist and flatten implementations determine the behaviour for border cases. These are discussed on the list page. The difference between ldepth 0 and 1 are not interesting to me at this moment anyway. Does anyone have an example where this difference is useful? The following quote from the list page might answer this question already: No program can tell the difference between the string "a" and the one-element list "a", because the one-element list "a" is the string "a".

escargo 2005-08-19: I had a situation where I had an application that could return one or more error messages in response to user input. At first I just returned a string with one error message. Then I discovered that I could not tell the different between a string with a multi-word error message and a list with multiple error messages. After that, I returned a list of length 1 with the first error message in it. While I recognize that everything is a string, sometimes I think that it should be possible to distinguish between strings and lists. Sometimes it has worked the other way, where something gets to be a list, but when I want to use it as a string, I can only get it without the curly braces if I do a [lindex item 0] to get the string item out of the list of length 1.

MJ - One way to solve this problem is by prepending the list with for example res so you will have:

 set res [list res $msg1]

 set res [list res $msg1 $msg2]

That way it will always be possible to see how many messages were returned even when the messages contain spaces. This leads to another observation on lists in Tcl: the only way to determine the depth of a datastructure built on lists, is by tagging the list elements.

PYK 2019-10-13: A deep list addresses this issue by using list to tag each item that that is meant as a single value rather than a nested structure.

Arts and Crafts of Tcl-Tk Programming

Category Discussion

Depth of a list

See Also

Description