Depth of a list

Difference between version 11 and 12 - Previous - Next
[Richard Suchenwirth] 2004-05-31:  How deeply nested is a [list]?


** See Also **

   [deep list]:   Addresses the issue of unambiguously representing a nested list versus a simple value that has the same representation as a nested 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:

======none
% 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]

or
 
 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.  In `[ycl list deep]`, which provides a set of routines to deal with this format, the caller controls the interpretation of a value when adding it:
======
lappend tree [list $item]
======

means "this is not a nested structure", whereas 

======
lappend tree $item
======

means "this is a nested structure if it looks like one."

<<categories>> Arts and crafts of Tcl-Tk programming | Discussion