Author:		Peter Spjuth <[email protected]>
State:		Final
Type:		Project
Vote:		Done
Created:	22-Oct-2018
Post-History:
Tcl-Version:	8.7
Tcl-Branch:	tip-523
Keywords:	queue, stack, pop
Vote-Summary:   Accepted 7/0/0
Votes-For:      DKF, BG, KBK, JN, DGP, FV, SL
Votes-Against:  none
Votes-Present:  none

---

Abstract

Add a command to efficiently remove an element from a list.

Rationale

Stacks and queues are common structures to use lists, and thus adding and removing elements are common operations. Adding has a direct command through lappend, while removing has less obvious commands, which also needs tricks like K to avoid performance problems.

A single command to both retrieve the value and remove it is simpler.

set x [lpop stack]

vs.

set x [lindex $stack end]
set stack [lrange $stack 0 end-1]

or even

set stack [lrange [K $stack [set stack {}]] 0 end-1]

To support both queue and stack the pop end needs to be chosen, and the easiest way is to have an index argument. This trivially extends the functionality to remove any element.

Further, making it use multiple indices in the same way as lindex and lset does gives more symmetry. Together with lset's ability to append to a sublist, doing push/pop on a sublist becomes feasible. The ability in lset and lindex to get an index list is not supported since argument expansion covers that usage.

Since deleting last is rather common (stack) and also the cheapest operation, that is selected as default when no index is given.

Specification

A new command is added to the core with the following format.

lpop listVar ?index ...?

The given indices are resolved to an element in the same way as lindex/lset does, except an index list is not supported, just plain index arguments. The return value is the element at index, and the list is modified to remove that element. If no index is given, the default is "end". An out of range index is an error.

Discussion

Name

Many alternative command names have been proposed.

lpop, ltake, lremove, ltrunc, (the bikeshed is Hunter Green #355E3B)

No name will ever fully explain what it does or match all users' expectations of what that name means. "lpop" is close enough and short.

Error

Should an out of range index be an error or a no-op returning the empty string?

Empty, for symmetry with lindex.

"It has always seemed wrongheaded to me that commands like lindex return the empty string when no element exists"

Moreover, lpop is not just reading like lindex, it is also removing and there the symmetry is not evident. By comparison, lreplace gives an error for too high indices.

Pop Multiple

It was proposed to be able to pop more than one element. This could be an index list in last index, or an option:

lpop listVar ?index ...? {0 1)
lpop -n 2 listVar
lpop -gather {0 3 7} listVar

This should take careful consideration since having a command that sometimes returns a list and sometimes an element should not be taken lightly. Any of the above versions are possible extensions to the current TIP, but are outside its scope.

Copyright

This document has been placed in the public domain.