Updated 2011-10-23 11:17:13 by RLE

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 lindexing 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, e.g. set s {a b {a b {a b c {a, e.g. set s {a b {a b {a b c {a d e c {a b c} c}}} d e} d e c {a b c} c}}} d e}```

Michael Schlenker likes to do things a bit faster; this is between 5 and 25 percent faster (with 8.3 and 8.4b1) than the solution above, by using foreach/incr instead of for/lindex:
``` 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 -1gs a bit faster; this is between 5 and 25 percent faster (with 8.3 and 8.4b1)
than the solution above, by using [f
}```

[serol] 2010-11-19: I needed a slightly modified lrsearch to get the number of occurrences of string in a nested list.
``` proc lrsearch2 {liste el} {
#get occurences in liste
set count [llength [lsearch -all -inline \$liste \$el]]

foreach ilist \$liste {
if {![atomic? \$ilist]} {
incr count [lrsearch2 \$ilist \$el]
}
}
return \$count
}```