TIP #22 Version 1.15: Multiple Index Arguments to lindex

This is not necessarily the current version of this TIP.

Abstract

Obtaining access to elements of sublists in Tcl often requires nested calls to the lindex command. The indices are syntactically listed in most-nested to least-nested order, which is the reverse from other notations. In addition, the nesting of command substitution brackets further decreases readability. This proposal describes an extension to the lindex command that allows it to accept multiple index arguments, in least-nested to most-nested order, to automatically extract elements of sublists.

Rationale

The heterogeneous nature of Tcl lists allows them to be applied to a number of useful data structures. In particular, lists can contain elements that are, themselves, valid lists. In this document, these elements are referred to as sublists.

Extracting elements from sublists often requires nested calls to lindex. Consider, for example, the following Tcl script that prints the center element of a 3-by-3 matrix:

    set A {{1 2 3} {4 5 6} {7 8 9}}
    puts [lindex [lindex $A 2] 2]

When these calls are deeply nested - e.g., embedded in an expr arithmetic expression, having results extracted through lrange, etc. - the results are difficult to read:

# Print the sum of the center indices of two 3x3 matrices
set p [expr {[lindex [lindex $A 2] 2] + [lindex [lindex $A 2] 2]}]

# Get all but the last font in the following parsed structure:
set pstruct {text {ignored-data
                      { ... }
		       }
		       {valid-styles
			   {justifiction {left centered right full}}
			   {font {courier helvetica times}}
		       }
		 }
return [lrange [lindex [lindex [lindex $pstruct 1] 2] 2] 0 end-1]

Note that the list of indices in the latter example is listed in the reverse order of vector indices. In most other languages/domains, the last line might take on one of the following forms:

return list_range(pstruct[2][2][1], 0, end-1);

return pstruct[[2, 2, 1]][[0:-1]]

temp = pstruct(2, 2, 1);
result = range(temp, 0, length(temp) - 1);

Allowing the lindex command to accept multiple arguments would allow this more-natural style of coding to be written in Tcl.

Specification

1. Allow lindex to accept an arbitrary number of arguments.

   1. The first argument (the list argument) must be a proper Tcl list. No change is required from current behaviour.

   2. The remaining arguments (the index arguments) must be proper list indices (either integer, end, or end-integer).

2. When only one index argument is given, the behaviour is unchanged from the current lindex command.

3. When multiple index arguments are given, the behaviour is defined recursively as:

   lindex alist i0 i1 i2 ... === lindex [lindex alist i0] i1 i2 ...
   

   Note that this does not define any restrictions on the implementation, which may be recursive or iterative.

4. When an invalid index is given, an error of the form, bad index "invalid_index": must be integer or end?-integer?, where invalid_index is the first invalid index encountered, must be returned.

5. If the list argument is malformed, the error resulting from an attempt to convert the list argument to a list must be returned. This behaviour is unchanged from the current implementation.

Side Effects

1. Whether the result of the lindex operation is successful, the underlying Tcl_Obj that represents the list argument may have its internal representation invalidated or changed to that of a list.

Comments

Don Porter <dgp at users dot sourceforge dot net>

I agree that it would be helpful to many programmers to provide a multi-dimensional array data structure that can be accessed in the manner described in this TIP. In the struct module of tcllib, several other data structures are being developed: graph, tree, queue, stack. I would support adding another data structure to that module that provides an interface like the one described in this TIP, with the intent that all of these helpful data structures find their way into the BI distribution.

I don't see any advantage to adding complexity to [lindex] as an alternative to development of a multi-dimensional array structure. Without a compelling advantage, I'm inclined against making [lindex] more complex. I like having Tcl's built-in commands provide primitive operations, and leave it to packages to combine the primitives into more useful, more complex resources.

This TIP should also consider how any changes to [lindex] mesh with the whole [listx] overhaul of Tcl's [list] command that has been discussed.

Dave Cuthbert <dacut at kanga dot org> responds

Don makes a good point -- with a good set of data structures in tcllib, the need for this TIP is lessened or even eliminated. Nonetheless, I see this as a way of implementing the structures he describes. In other words, a more powerful primitive (which, in reality, adds fairly little complexity when measured in number of lines of code changed) would benefit these structures.

As for the [listx] overhaul, there are many competing proposals for the specification it is difficult to come up with a metric. In writing this TIP, I assumed a vacuum -- that is, a listx command would not be added to the core in the near future.

Donal K. Fellows <fellowsd at cs dot man dot ac dot uk> points out

Although there is tcllib and [listx] to think about, they are certainly not reasons for rejecting this TIP out of hand. The availability of tcllib is not currently anything like universal (not stating whether this is a good, bad or ugly thing) and all the [listx] work will need its own TIP to make it into the core (you tend to have availability problems if it is an extension.) It is not as if the core is short of syntactic sugar right now (the [foreach] command is ample demonstration of this.)

Don Porter <dgp at users dot sourceforge dot net> follows up

I'll leave the discussion above in place so the history of this TIP is preserved, but I have withdrawn my objection.

There was quite a discussion on news:comp.lang.tcl about using lindex to return multiple arguments. For example:

 % set list {a {b1 b2} c d e}
 % lindex $list 1
 b1 b2
 % lindex $list 1 0
 {b1 b2} a
 % lindex $list {1 0}
 b1

In other words, the list index arguments can, themselves, be lists. Only when the argument is a list would the "recursive selection" procedure of the TIP be used. For multiple arguments, the behaviour is akin to

 lindex $list a b c  ->
      list [lindex $list a] [lindex $list b] [lindex $list c]

Summarised by Dave Cuthbert <dacut at kanga dot org>

Donal K. Fellows <fellowsd at cs dot man dot ac dot uk> points out

The problems with the above version of multiple indexing are that it loses the property that [lindex] always returns a single element (making writing robust code harder) and that it forces use of the [list] constructor a lot or inefficient type handling when some of the indices must be computed. Then there is the whole question of what happens when you have indexes that are lists of lists, which is a major can of worms.

Luckily, we could always put this sort of behaviour into a separate command (e.g. called [lselect]) which addresses at least the majority of my concerns, and which (in my opinion) need not even form part of this TIP.

Notes on History of this TIP

This TIP was originally written by Dave Cuthbert <dacut at kanga dot org>, but ownership has passed (beginning of April) to Kevin Kenny <kennykb at acm dot org>.

Copyright

This document has been placed in the public domain.

This is not necessarily the current version of this TIP.