[Richard Suchenwirth] 2002-07-17 - Since Tcl 8.4, [lindex] and the new [lset] command take multiple indices to retrieve or modify an element in a nested [list], which might be used to represent a multi-dimensional table (matrix, database) or a tree structure. To complement these two new goodies, here's a recursive [lsearch] that returns an index list, of the first occurrence of the wanted item, as can be used by [lindex] or [lset], or -1 if the element was not found.

Note that the search goes down as long as an element can be interpreted as a list of more than one element, so intended strings like "John F Kennedy" will also be searched, e.g. for F.
Note also that the result often is a list, so comparisons should be limited to == -1 or != -1.

 proc lrsearch {list el {prefix {}} } {
    set pos [lsearch $list $el]
    if {$pos != -1} {return [concat $prefix $pos]}
    for {set i 0} {$i<[llength $list]} {incr i} {
	set ilist [lindex $list $i]
	if {![atomic? $ilist]} {
	    set pos [lrsearch $ilist $el [concat $prefix $i]]
	    if {$pos != -1} {return $pos}
	}
    }
    return -1
 }
To prevent endless recursion, but still handle lists that have only one element on higher level, the ''atomic?'' test was introduced: it is true if the first element of the list is equal to the list itself, so that no further [lindex]ing could bring any new facts.

 proc atomic? {list} {string equal $list [lindex $list 0]}

----
 % lrsearch {a b {c {d e}}} a
 0
 % lrsearch {a b {c {d e}}} b
 1
 % lrsearch {a b {c {d e}}} c
 2 0
 % lrsearch {a b {c {d e}}} d
 2 1 0
 % lrsearch {a b {c {d e}}} e
 2 1 1
 % lrsearch {a b {c {d e}}} f
 -1
 % lrsearch {a {{b c}} d} b
 1 0 0
----
[Michael Schlenker] likes to do things a bit faster, this is between 5 and 25 percent faster (with 8.3 and 8.4b1) then the solution above:

 proc lrsearch2 {list el {prefix {}} } {
    set pos [lsearch $list $el]
    if {-1 != $pos} {return [concat $prefix $pos]}
    set i 0
    foreach ilist $list {
    if {![atomic? $ilist]} {
        set pos [lrsearch2 $ilist $el [concat $prefix $i]]
        if {-1 != $pos} {return $pos}
        incr i
    }
    }
    return -1
 }
----

[Additional list functions] | [Arts and crafts of Tcl-Tk programming]