TIP 351: Add Striding Support to lsearch

Bounty program for improvements to Tcl and certain Tcl packages.
Author:         Peter da Silva <peter@taronga.com>
Author:         Donal K. Fellows <donal.k.fellows@manchester.ac.uk>
Author:         Harald Oehlmann <harald.oehlmann@elmicron.de>
Author:         Andreas Leitgeb <avl@logic.at>
State:          Draft
Type:           Project
Vote:           Pending
Created:        09-Jul-2009
Tcl-Version:    8.7


This TIP allows the searching of lists that are grouped into collections of several elements.


When operating on strided lists (for example key-value lists) it's normal to convert them between lists and arrays and back again. If it was possible to efficiently perform a strided search of the list it would be possible to (for example) search just the keys and ignore the values. Indeed, Tcl has a long tradition of working with lists which are structured into groups through foreach and array get, and this is strengthened further with dictionaries [111] and striding sorts [326]. However, there is currently no facility for searching such lists; this TIP proposes fixing this.

Proposed Change

We propose adding a -stride option to lsearch, by exact analogy with the option added to lsort in [326], whose semantics it should closely match.

If -stride is supplied, the list will be treated as consisting of groups of grpSize elements. The search will be operated within this group as it is a first level of nested lists (see Conceptual Backround below).

The first element of -index is used to seach for an item of the group.

The option -start always points to the beginning of the group, even if a position within the group is given.

Returned indices are the first element of the striding group(s) that is/are being indicated.

The list length must be a multiple of grpSize, which in turn must be at least 2.

Conceptual Backround

Striding equivalent to first level of nested lists

The striding within the list is seen as the first level of list nesting. E.g.

Nested list:

set deep {{1 a A} {2 b B} {3 c C}}

Flat strided list:

set flat {1 a A 2 b B 3 c C}

Functions should operate the same way on both representation, with the only difference, that -stride 3 must be specified in the second case.

Unfortunately, the current implementation of lsort is not doing this. It interpretes -index "" as -index 0:

% lsort -stride 2 {A 1 A 2 A 0}
A 1 A 2 A 0
% lsort -stride 2 -index "" {B 2 B 1 A 3}
A 3 B 2 B 1

Numeric position indices

Numerical positional indices (-start parameter, return value) follow the flattened list and not the grouped list. This is different to the nested list view.

Furthermore, if option -subindices is given and a non-empty argument for -index, then the group-start and index-into-group are added up. This gives compatibility with lindex, as in the no-stride case.


In these examples, the variable kvlist holds the key-value list:

set kvlist {K1 V1 K2 V1 K1 K1}

Example 1: find keys even if they exist multiple times:

% lsearch -all -stride 2 -index 0 -exact $kvlist K1
0 4

Example 2: find existance of a value:

% lsearch -all -stride 2 -index 1 -exact $kvlist V1
0 2

Remark that the indexes of the first group elements are returned. The real values are at "result+index" eq 1 3.

Example 3: extract a sub-kv-list starting from key K2:

% lrange $kvlist [lsearch -stride 2 -index 0 -exact $kvlist K2] end
K2 V1 K1 K1

Example 4: find a group within a list:

% lsearch -stride 2 -exact $kvlist {K2 V1}

Example 5: find in combined strided and nested list

% lsearch -stride 2 -index {1 1} -exact\
        {K0 {V0.0 V0.1} K1 {V1.0 V1.1}}\

Example 6: subindices with strided list:

% lsearch -stride 2 -index {1 1} -subindices {1 {a A} 2 {b B}} B
3 1   (that is: 2 for the group-start plus 1 for the intra-group
       index, and separately 1 for the further nested index.
% lindex {1 {a A} 2 {b B}} 3 1

to be consisten with:

% lsearch -index {1 1} -subindices {{1 {a A}} {2 {b B}}} B
1 1 1
% lindex {{1 {a A}} {2 {b B}}} 1 1 1


This document has been placed in the public domain.