lsearch

lsearch searches for elements in a list that match a pattern.

Synopsis

lsearch ?option? list pattern

Options

MATCHING STYLE OPTIONS

-exact
pattern is a value to match exactly. Useful for searches involving *
-glob
-regexp
pattern is a regular expression
-sorted
requires the list to be sorted, and does faster binary search.

GENERAL MODIFIER OPTIONS

-all
returns the indices of all matches, or, with ''-inline, a list of matching elements
-inline
returns a list of matching element(s), or the empty string (not -1!) if nothing found
-not
-start index

CONTENTS DESCRIPTION OPTIONS

-ascii
-dictionary
-integer
-nocase
case is not be considered when matching the pattern. Introduced in Tcl 8.5.
-real

SORTED LIST OPTIONS

-decreasing
-increasing
-bisect

NESTED LIST OPTIONS

-index indexList
-subindices

Description

The simplest invocation form for lsearch is:

lsearch list search_term

lsearch returns the index of the first element in list that that matches pattern, or -1 if there are no matches.

In the following example, lsearch behaves much like grep:

lsearch -regexp -inline -all $lines $regexp

Before Tcl 8.5 introduced the in operator, lsearch was very frequently used to test for the existence of a value in a list.

Examples

Index return mode (default)

In the following example the result is 0 because the count starts from zero and RedHat is the first element in the list. SUSE would return 1 and Slackware would return 6.

set distros {RedHat SUSE Debian Knoppix Peanut Mandrake Slackware}
lsearch $distros RedHat

When no match is found, lsearch returns -1 (minus one), so in order to check the presence of an element in the list:

if {[lsearch $distros Debian] >= 0} {
     puts {Debian is in the list}
} else {puts {There is no Debian in the list}}

RedHat is mixed with upper and lower-case letters, for such case the -nocase option introduced since Tcl 8.5 might be useful. Before Tcl 8.5, one has to use regular expression to do case-insensitive lsearch. The method is introduced in later part of this page.

-inline value return mode

-inline makes lsearch return the matching element instead of its index:

lsearch -inline $distros *ware

The result is Slackware.

By default, lsearch returns only the first matching element. To obtain all matches, use -all:

lsearch -all $distros *an*

The result is 2 4 5, indicating the matches Debian, Peanut and Mandrake.

-all + -inline return mode

Combine -all with -inline and get all names instead of all indices:

lsearch -all -inline $distros *an*

The result is Debian Peanut Mandrake

And if you want a list without a Peanut:

lsearch -all -inline -exact -not $distros Peanut

gives you

RedHat SUSE Debian Knoppix Mandrake Slackware

no matter where (or how many times) Peanut is in the list.

Default comparison mode

The default for lsearch is -glob . However, be certain the glob behavior is what you expect.

For instance, check out this code.

set a [list field1:val1=field3 field2:val2=2 field3:val3=3 field3]
set b [lsearch $a field3]
puts $b

Would you expect glob to mean that element 0, 2, or 3 would be returned? 3 is the answer you get. On the other hand,

set b [lsearch -regexp $a field3]
puts $b

The result is 0.

Case-insensitive lsearch

Use (?i) in the -regexp for case-insensitive comparison:

% lsearch -regexp {Foo Bar Grill} (?i)^BAR$
1

From Tcl 8.4, fancy new modes have been added: -all gives you all instances (instead of the first only); -inline gives a list of the elements themselves instead of their index. So a very easy filter that removes empty sublists from a list is lsearch -all -inline $list ?* ;# RS - example:

% lsearch -all -inline {foo {} bar {} grill} ?*
foo bar grill

AMG: Or use -not like so: lsearch -all -not -inline {foo {} bar {} grill} {}

Discussion

Bells and/or whistles

From 8.5 on there will be even more switches, for example TIP 127 -index option.

JMN 2005-12-11: Along with new commands like lrepeat. this makes Tcl pretty neat for manipulating matrices (nested lists). e.g

set m [lrepeat 3 [lrepeat 3 0]]
% {0 0 0} {0 0 0} {0 0 0}
lset m 1 0 1 ; lset m 2 0 2
% {0 0 0} {1 0 0} {2 0 0}

Now you can retrieve in columnwise fashion like this:

lsearch -all -inline -subindices -index 0 $m *
%0 1 2

But it seems a bit funny to be using lsearch in 'glob' mode when we are really wanting to do positional access. Without resorting to extensions.. is there a better way?

schlenk Simply lindex is enough:

list [lindex $m 0 0] [lindex $m 1 0] [lindex 2 0]

Nested lists

LV: I'm trying to figure out whether lseach can help search a nested list.

set nl [list [list a 100% red] [list b 96.8 yellow] [list c 3.1415 green]]

proc whereis {nlist srcterm} {
   return [lsearch -nocase $nlist $srcterm]
}

% whereis $nl yellow
-1

That's not what I was wanting. What I would like to get is 1 - yellow is in the second sublist of $nl in this case.

I don't want to limit the search to one element of each sublist. Do I have to write a lsearchn which loops through all the nested lists and do a lsearch on each one?

# Takes same arguments as lsearch, but treates each word
# as if it were a single depth sublist to lsearch.
# Limitations: should handle any depth
#              return value should be different depending on options, etc.

proc lsearchn args {
    set argc [llength $args]
    set patt [lindex $args end]
    set list [lindex $args end-1]
    set options [lrange $args 0 end-2]
    set index 0
    foreach sublist $list {
        set return [lsearch {*}$options $sublist $patt]
        if {$return != -1} {
           break
        }
        incr index
    }
    if {$return == -1} {
        set index -1
    }
    return $index
}

There's probably a lot of error handling, etc. that needs to be done there.

MJ: This was using strings as lists at several places without making sure they were actual valid lists (as argument to foreach and as argument to lsearch). Added some splits to remedy this.

proc lsearchn {args} {
    set argc [llength $args]
    set patt [lindex $args end]
    set list [split [lindex $args end-1]]
    set options [lrange $args 0 end-2]
    set index 0
    foreach sublist $list {
        set sublist [split $sublist]
        set return [lsearch {*}$options $sublist $patt]
        if {$return != -1} {
           break
        }
        incr index
    }
    if {$return == -1} {
      set index -1
}
 return $index
}

MJ - Note that split is not always the intended way to create a list from the string, especially when the string contains multiple spaces in a row or newlines. If you have data like that, use the first version. However, you need to pass a valid list whose elements are also valid lists. If this is not the case an error will be thrown. If you have control over the data coming into this proc (e.g. you create the lists yourself) the best way is to make sure the list and its elements are valid lists. Note this is not how to do it:

# e1 and e2 contain elements of the sublist
# slx are the sublists
set sl1 "{$e1 $e2}"
set list "{$sl1 $sl2 sl3}"

This is

# $slXeX are elements of the sublist X
set list [list [list $sl1e1 $sl1e2] [list $sl2e1 $sl2e2]]

Summarizing if you intend to use something as a list, make sure that it is a valid list when creating or storing it, this will save you a lot of hassles later.


LV 2007-12-20

Here's the problem I'm working on. I've used array get to get a list consisting of a set of keys and values. Ideally, what I want to do is search only the values. Not only that, but I want to be able to search the values ignoring case. And, just to make things even more difficult, I need to be able to provide a substring of data in the entry.

So, for example, let's say that we have:

set contents [list PROJECT ABC123 LEADER JDOE DESCRIPTION [list SCREENSAVER SOFTWARE] RELEASE_COORD JSMITH]

So, I need to be able to look for "abc" or "doe" and find a match here.

I modified a version of the in proc to be:

proc in {list elements} {
    expr {[lsearch -nocase -glob [append "*" ${list} "*"] $elements] >= 0}
}

set searchkey abc

if {[in $contents $::searchkey]} {
   myprint $contents
}

but this doesn't ignore the key fields, and doesn't seem to do the substring thing right. Anyone have some ideas how to get closer to what I am wanting?

Matching multiple patterns against a word

newp: I am trying to avoid a loop and wonder if there is a way: Suppose my list contains patterns and I would like to see if a particular instance occurs in that list. The -regexp option does not help since it does the matching the opposite way. Say:

set l [list john* james* and*]
lsearch $l "johnson"
  • should match james* entry in the list lsearch $l "anderson"
  • should match "and*" in the list and so on

LV: are you certain you don't mean that johnson should match john* ?

newp Yes, you are right: it should match john*. I am just learning how to edit these wiki pages.

AMG: This is still unanswered. Someone should chip in.

lsearch -bisect -real

AMG: Here's a limited, slow Tcl 8.4 implementation of lsearch -bisect -real:

if {[catch {lsearch -bisect -real {} 0}]} {
    proc lsearchBisectReal {list value} {
        if {[set index [lsearch -real -sorted $list $value]] < 0} {
            expr {[lsearch -real -sorted\
                    [lsort -real [linsert $list end $value]] $value] - 1}
        } else {
            return $index
        }
    }
} else {
    proc lsearchBisectReal {list value} {
        lsearch -bisect -real $list $value
    }
}

lsearch -stride, key-value pairs

HaO 2012-04-20 Within Tcl8.6, there will be lsort -stride to process key-value pairs. TIP #351 'Add Striding Support to lsearch' proposes the same extension for lsearch.

Here are some implementations which check the returned index to match a stride condition.

# lsearch -stride $stride -index $index {*}$args list needle
proc lsearch_stride {list needle {stride 2} {index 0} args} {
    set pos 0
    while {-1 != [set pos [lsearch -start $pos {*}$args $list $needle]]} {
        if {$index == ($pos % $stride)} {
            return $pos
        }
        incr pos
    }
    return -1
}
% lsearch_stride {A 1 B B} B
2
% lsearch_stride {A 1 B B} 1
-1
% lsearch_stride {A 1 B B} A
0
% lsearch_stride {A 1 B B} B 2 1
3
# lsearch -stride $stride -index $index -all {*}$args list needle
proc lsearch_stride_all {list needle {stride 2} {index 0} args} {
    set resultlist {}
    foreach pos [lsearch -all {*}$args $list $needle] {
        if {$index == ($pos % $stride)} {
            lappend resultlist $pos
        }
    }
    return $resultlist
}

% lsearch_stride_all {A 1 B B B C} B
2 4
% lsearch_stride_all {A 1 B B B C} C 2 1
5

AMG: What is the status of [lsearch -stride]? I sure could use it now. The TIP is now approaching six years old, so I'm shocked it's still a draft without a vote or reference implementation.

AMG, five years later: I guess [lsearch -stride] is going into Tcl 8.7.

lsearch -command

AMG: How about -command? Even with the addition of -stride, [lsearch] is still lagging behind [lsort] in terms of parallel functionality.

See Also

list
lappend
lindex
linsert
llength
lrange
lreplace
lsort
Recursive list searching
gives you an index vector which can be used with lindex/lset.