'''Additional [list] functions''' is a guide to pages that provide commands and scripts or present methods for manipulating [list%|%lists]. ** Command Suites ** Collections of list commands. [aqtools]: [ExtraL]: [fptools]: `lcompare`, `lempty?`, `lmultirange`, `lreduce`, `lsample`, `lshift!`, `match` (for [pattern matching] on lists) and others. [https://web.archive.org/web/20080625075946/http://www.han.de/~racke/jultaf/jultaf.html%|%Jumble Library for Tcl and Friends], by Stefan Hornburg: `shift`, `pop`, `append`, `assign`, `match` [Listx]: Provides the essential extended set of list operations. Today, most are in Tcl itself. [Listex], by [Stuart Cassoff]: `lPluck`, `lDivide`, `lDivideAtStr`, `lUInterleave`, `lMaxelementLength`. [ftp://ccfadm.eeg.ccf.org/pub/ctk/mtcl.tar.gz%|%mtcl]: ([HaO] 2010-08-24: dead link for me) [http://www.purl.org/net/akupries/soft/pool/index.htm%|%Pool]: [http://www.purl.org/net/akupries/soft/pool/pkg_Pool_Base.htm%|%Pool_Base]: [tcllib%|%tcllib's] [struct::list]: [TclX]: Search the [http://www.tcl.tk/man/tclx8.2/TclX.n.html%|%documentation] for ''LIST MANIPULATION COMMANDS''. [underscore.tcl]: [ycl]::list: provides commands such as `dedent`, `any`, `all`, `are`, `filter`, `pick`, `[scripted list%|%sl]`, and `which`. ** Modification Commands **Commands that modify the content of a list. * [lpop]: [lpop]: [lremove]: [lshift -Adding Unique Items to Lists of Fixed Length]: * [another list comprehension]: * [Finding a sublist]: [another list comprehension]: ** Traversal Commands **Commands that visit elements in a list. [Finding a sublist]: [lazy lists]: [List Comprehension]: [list map and list grep]: two operations implemented (over-)simply in Tcl. [lswitch]: Like `[switch]`, but each ''pattern'' is a list of patterns to match against the item in ''string'' at the corresponding position. All switch options are supported. [range], by [Salvatore Sanfilippo]: [Python]-like range operation. [Recursive list searching]: [Striding a list]: * [Use while to iterate over a list]: [Use while to iterate over a list]: ** Reording Commands **Commands that reorder the elements of a list. * [randomizing a list]: * [Shuffle a list]: * [Shuffle a list: graph results]: * [Shuffling a list]: [randomizing a list]: * [list stripping]: [Shuffle a list]: [Shuffle a list: graph results]: [Shuffling a list]: [Sorted Lists]: [lrotate%|%Rotate a list%|%]: * [List trim]: * [lsplit]: creates two lists from a single list and a test expression * [MakeRanges]: Takes a list of numbers and makes them into a a list of number ranges. [Concatenating lists]: * [AsserTcl]: Supports quantifier commands to test whether an expressions holds universally or existentially over a data structure such as a list or array aggreggate data structure. [list stripping]: * [Cartesian product of a list of lists]: [List trim]: * [Counting Elements in a List]: [lsplit]: creates two lists from a single list and a test expression [MakeRanges]: Takes a list of numbers and makes them into a a list of number ranges. [nested list join]: [permutations]: [Power set of a list]: [split and join for nested lists]: [Using expr on lists]: [Summing a list]: [Unique Element List]: [lolcat]: Process a list into another list that contains more values than the original list. * [Depth of a list]: * [diff in Tcl]: longest common subsequence * [ftp://ftp.tcl.tk/pub/tcl/mirror/ftp.procplace.com/sorted/packages-7.6/devel/keylprint.README%|%key list printing procedures]: pretty prints Tclx's [http://www.tcl.tk/man/tclx8.2/TclX.n.html%|%key lists]. [AsserTcl]: Supports quantifier commands to test whether an expressions holds universally or existentially over a data structure such as a list or array aggreggate data structure. * [Complex data structures] for [struct]: Named access to list positions. [Cartesian product of a list of lists]: * [Decision trees]: [Counting Elements in a List]: * [keyed list]: [Depth of a list]: [diff in Tcl]: longest common subsequence [ftp://ftp.tcl.tk/pub/tcl/mirror/ftp.procplace.com/sorted/packages-7.6/devel/keylprint.README%|%key list printing procedures]: pretty prints Tclx's [http://www.tcl.tk/man/tclx8.2/TclX.n.html%|%key lists]. [ldiff]: Find the difference of two lists. [lexpr]: [list level]: [ldiff], by [PL]: Find the difference of two lists. [plist]: is for lists what `[parray]` is for arrays. * [linked lists]: * [Chart of proposed list functionality]: [Binary trees]: * [internal organization of the list extension]: [Bit vectors]: Can nicely be implemented with lists. * [list]: Contains (pointers to other Tcl specific list related commands. [Complex data structures] for [struct]: Named access to list positions. [Decision trees]: [keyed list]: [linked lists]: [nxs]: Nested heterogeneous data structures. [set operations for Tcl lists]: [Stacks and queues]: [trees as nested lists]: [yet another stack package]: * [Showing sublists]: In a listbox. [Chart of existing list functionality]: [Chart of proposed list functionality]: [LV]: Anyone have a URL for this ''posting'' of forest.tcl ? [internal organization of the list extension]: [list]: Contains (pointers to other Tcl specific list related commands. [Showing sublists]: In a listbox. ---- Outline of the next steps to do: * Go through extensions listed above and collect all of their functionality in a table. Group equal and/or similar functionality together. [Chart of existing list functionality] * Define the functionality we want to have in the official extension. (Or shall we skip this in favor of a '''take all''' approach ?). -- AK: No. After looking at the available functionality I believe that some parts may need a little pruning. [Chart of proposed list functionality]. * Implement the functionality. Areas of discussion: * What functionality is provided, what do we want, what is missing, or superfluous ? LV already started a wishlist, see below. * [Internal organization of the list extension], commenting style, which namespace, ... ---- [LV]: Another useful thing would be a 'wishlist' (excuse the pun) of functionality requested. This would include things like (all of these have, in the past, either been posted to the newsgroup or offered by a contributor to the newsgroup - so if code is desired, the contacts listed in [http://www.purl.org/net/tcl-faq/part5.html] should be emailed.): * [lassign] - Assign [elements] of list to the given variables. -- AK: Already provided by some extensions. RS: ... or [foreach]. [DKF]: In the core in 8.5. * linear sort on list of lists - Alphanumeric comparison for linear sort of lists. -- AK: '''???''' [Lars H]: Does this mean lexicographic sort? To compare elements L1 and L2, first compare their first elements [[lindex $L1 0]] and [[lindex $L2 0]]. If these are equal, compare the second elements, and so on. * Linked list support. I (AK) had a problem here, but Larry solved it for me. Meant is stack/queue-like access to the list. Some extensions already provide this functionality: [yet another stack package]. * Remove empty elements from list. -- '''NEW'''. Added to proposed list of functions. * Given one list, create a new list consisting only of the unique elements. -- AK: Provided by some extensions. [Lars H]: How is this different from [[lsort -unique]]? * Even better - provide list sorting capability equal or greater than Unix sort- -- '''NEW'''. AK: This will be difficult. * tclX code to return subsets of lists, based on patterns. -- AK: Provided by some extensions, but most not as complete as [TclX]. ([DKF]: This can be done with [lsearch]; '''[[lsearch -all -inline -glob $theList $theGlobPattern]]''') * parse a list into variables similar to the way a command line is parsed. -- AK: getopt-like, place in that extension. * Compare two lists for equality. -- '''NEW'''. AK: Looks so innocent. What is equality ? With order ? Without ? What about duplicates ? These are several functions. Not yet in the proposed list. * A number of people have written a variety of 'database query results' to 'list' type interfaces. I wonder if something generic could be created. * Transpose elements within list of lists -- AK: Primitives for that already provided by some extensions. * [ulis]: ldelete list-name ?index...?, remove the items in place. * [ulis]: leval $list, eval without concat. [DKF]: In Tcl 8.5, just use '''[[{*}$list]]''' which is now part of the core language syntax. ---- [AK]: I have to admit that I currently see ''keyed lists'' as something to either add later, or to place them into a separate extension. [AK]: I would also vote to definitely place DB interfaces into their own extension. DL: also look at list utilities in the opt package of tcl 8.[[01]] (mostly tclX 'compatible' though) ---- [Nat Pryce]: I have implemented ''map'', ''fold'' and ''zip'' functions in C and ''lambda'' functions in Tcl, but never released them. Anyone who is working on a list extension package is welcome to the code. ---- [Larry Virden]: the following pages have recently appeared on the Wiki: [Shuffle a list], [Striding a list], [Summing a list] - [Cartesian product of a list of lists] [Recursive list searching] ---- Here's some little helpers just for taking out: '''List element''': ====== proc lel {L element} {expr {[lsearch $L $element]>=0}} ====== ====== package require Tcl 8.5 proc lel {L element} { expr { $element in $L } } ====== Though if you have Tcl8.5 you should write `if {$elt in $list} ...` rather than `if {[[lel $list $elt]]} ...`. '''Add an element to a list''' only if not present yet: ====== proc ladd {_L args} { upvar $_L L if {![info exists L]} {set L {}} foreach i $args {if {![lel $L $i]} {lappend L $i}} } ====== '''Random element''' selected from a list: ====== proc lrandom L {lindex $L [expr {int(rand()*[llength $L])}]} ====== '''Random element''' drawn (and removed) from a list: ====== proc ldraw {_L} { upvar 1 $_L L set pos [expr {int(rand() * [llength $L])}] set res [lindex $L $pos] set L [lreplace $L $pos $pos] set res } ====== '''Remove elements from a list''' by value: ====== proc lremove {_L args} { upvar $_L L foreach i $args { set pos [lsearch $L $i] ;# might be -1 if not found... set L [lreplace $L $pos $pos] ;# ... but that's fine } } ====== '''[lreverse%|%Reverse] the order of a list''': Since 8.5, `[lreverse]` is a [Tcl Commands%|%built-in] Tcl command. ====== proc lreverse L { set res {} set i [llength $L] #while {[incr i -1]>=0} {lappend res [lindex $L $i]} while {$i} {lappend res [lindex $L [incr i -1]]} ;# rmax set res } ;# RS, tuned 10% faster by [rmax] ====== Here's a simpler way to do it. ====== proc lreverse2 l { set ret {} foreach i $l { set ret [linsert $ret 0 $i] } return $ret } #EAS ====== [RS]: Note however that the `[linsert]` requires copying the whole sublist N times, while, the `[lappend]` copies each element exactly once. [KPV]: Here are three more ways of reversing a list that utilize [lset] to swap pairs of elements in place: ====== proc lreverse3 {l} { set start -1 set end [llength $l] while {[incr start] < [incr end -1]} { set tmp [lindex $l $start] lset l $start [lindex $l $end] lset l $end $tmp } return $l } ====== For long lists you can squeeze out a bit more performance with the help of `[foreach]`: ====== proc lreverse4 {l} { set start -1 set end [llength $l] foreach tmp $l { if {[incr start] >= [incr end -1]} break lset l $start [lindex $l $end] lset l $end $tmp } return $l } ====== Here's a very simple version — faster than `lreverse4` but alas not the fastest: ====== proc lreverse5 {l} { set end [llength $l] foreach tmp $l { lset l [incr end -1] $tmp } return $l } ====== [Lars H]: This is not fast, but it avoids index arithmetic. The idea can be nice in cases where you want to process the list elements while reversing their order. ====== proc lreverse6 {l} { set stack {} foreach item $l {set stack [list $stack $item]} set res {} while {[llength $stack]} { foreach {stack item} $stack break lappend res $item } return $res } ====== '''Sort a list on multiple indices''': ====== proc multisort {indices L args} { set cmd "list $L" foreach i [lreverse $indices] { set cmd "lsort $args -index $i \[$cmd\]" } eval $cmd } ;# RS ====== ======none % multisort {2 0 1} {{abe zyx 25} {john smith 14} {harold brown 99} {mary jones 32}} {john smith 14} {abe zyx 25} {mary jones 32} {harold brown 99} % multisort {0 2 1} {{abe zyx 25} {john smith 14} {harold brown 99} {mary jones 32}} -decreasing {mary jones 32} {john smith 14} {harold brown 99} {abe zyx 25} ====== see also: [Custom sorting] ---- '''Permute a list''': returns a list of the possible orderings of the input list, e.g. `lpermute {a b c} => {{a b c} {a c b} {b a c} {b c a} {c a b} {c b a}}`. Be aware that the output length grows factorially, so a 7-element input produces over 5000 permutations... ====== proc lpermute L { if {[llength $L] < 2} { set res $L } else { set pos 0 foreach i $L { set rest [lreplace $L $pos $pos] incr pos foreach j [lpermute $rest] { lappend res [concat [list $i] $j] } } } set res } ;# RS ====== ''Find the list element numerically closest to a given value''' [[F]or a given value, find one element from a given list with minimal absolute difference [[...] ====== proc closest {value list} { set minElement [lindex $list 0] set minDist [expr {abs($value-$minElement)}] foreach i [lrange $list 1 end] { if {abs($value-$i) < $minDist} { set minDist [expr {abs($value-$i)}] set minElement $i } } set minElement } In borderline cases, it picks the first hit, though: % closest 2.5 {1 2 3 4 5} 2 ====== ---- '''Compact an integer list:''' merge consecutive numbers, if more than two, into a dash-separated range (an extra element is appended to the list to collect the final buffer): ====== proc rangify list { set res {} set buf {} foreach i [lappend list {}] { if {$buf eq {} || $i == [lindex $buf end] + 1} { lappend buf $i } else { if {[llength $buf] > 2} { set buf [lindex $buf 0]-[lindex $buf end] } lappend res $buf set buf $i } } join $res } ;#RS ====== ======none % rangify {1 2 3 5 6 7 9 10 12 13 14 17 18 19} 1-3 5-7 9 10 12-14 17-19 ====== Here's an alternative remake of October 2005, with an expander, too: ====== proc compress list { set res [lindex $list 0] for {set i 1} {$i < [llength $list] - 1} {incr i} { set it [lindex $list $i] if {$it == [lindex $list [expr {$i-1}]] + 1 && $it == [lindex $list [expr {$i+1}]] - 1} { lappend res - } else {lappend res $it} } lappend res [lindex $list end] regsub -all -- { - (- )*} $res - } #---- For the way back: proc expand clist { set res {} foreach part $clist { if [regexp {([0-9-]*[0-9])-(.+)} $part -> from to] { while {$from <= $to} {lappend res $from; incr from} } else {lappend res $part} } set res };# RS ====== ---- '''List constructor:''' After the advent of multi-index [lindex] and [lset], nested lists can conveniently be used e.g. for matrixes, but all list elements must be present for them to work. Here's a nestable constructor that fills a list with the specified initial value: ====== proc lrepeat {value number} { for {set i 0} {$i<$number} {incr i} { lappend res $value } set res } ;# RS % lrepeat foo 5 foo foo foo foo foo % lrepeat [lrepeat 0 5] 5 {0 0 0 0 0} {0 0 0 0 0} {0 0 0 0 0} {0 0 0 0 0} {0 0 0 0 0} ====== The second edition saves you the nesting, accepts indices in a list or separately, just like lset or lindex: ====== proc lrepeat {value args} { if {[llength $args] == 1} {set args [lindex $args 0]} foreach number $args { incr number 0 ;# force integer (1) set buf {} for {set i 0} {$i < $number} {incr i} { lappend buf $value } set value $buf } set buf } % lrepeat 0 3 4 {0 0 0} {0 0 0} {0 0 0} {0 0 0} % lrepeat 0 {3 4} {0 0 0} {0 0 0} {0 0 0} {0 0 0} % lrepeat 0 {3 4 5} {{0 0 0} {0 0 0} {0 0 0} {0 0 0}} {{0 0 0} {0 0 0} {0 0 0} {0 0 0}} {{0 0 0} {0 0 0} {0 0 0} {0 0 0}} {{0 0 0} {0 0 0} {0 0 0} {0 0 0}} {{0 0 0} {0 0 0} {0 0 0} {0 0 0}} ====== (1): See [Stress testing] for why this makes the code safer. [DKF]: Tcl 8.5a0 has a variation on this which behaves like this: ====== proc lrepeat {count value args} { set values [linsert $args 0 $value] set result {} for {set i 0} {$i < $count} {incr i} { eval [list lappend result] $values } return $result } ====== And now, because I can't resist it, here's an even hackier way to do it. :^D ====== proc lrepeat {count args} { set result {} set cmd [list eval [list lappend result]] for {set i 0} {$i < $count} {incr i} { lappend cmd $args } eval $cmd } ====== [AMG]: This second version is the more efficient of the two. It is also more correct in that it allows [[[lrepeat]]] to take only one argument (the count), in which case it returns empty string. Though to be pedantic, both are technically incorrect for Tcl 8.5a0 which predates TIP 323 [http://tip.tcl.tk/323]; back then, [[lrepeat]] arbitrarily rejected $count = 0. [FW]: Here's a most minimalist way (and of course the less efficient). ====== proc lrepeat {count args} {string repeat "$args " $count} ====== [AMG]: [DKF]'s "efficient" version does far more work than it has to. Here's a significantly faster approach: ====== proc lrepeat {count args} { set cmd [list concat] for {set i 0} {$i < $count} {incr i} { lappend cmd $args } eval $cmd } ====== And another version with a slightly faster loop: ====== proc lrepeat {count args} { set cmd [list concat] incr count while {[incr count -1]} { lappend cmd $args } eval $cmd } ====== Timing: ====== % info patchlevel ;# 8.6.1 % time {dkf_1 123 x y z} 10000 ;# 773.3324 microseconds per iteration % time {dkf_2 123 x y z} 10000 ;# 108.0783 microseconds per iteration % time {amg_1 123 x y z} 10000 ;# 27.1447 microseconds per iteration % time {amg_2 123 x y z} 10000 ;# 21.9983 microseconds per iteration % time {lrepeat 123 x y z} 10000 ;# 3.5693 microseconds per iteration ====== And for a laugh, here's the time for [FW]'s less efficient approach: ====== % time {fw_1 123 x y z} 10000 ;# 2.4697 microseconds per iteration ====== Yup. It's faster than the native [[lrepeat]]! But the return value is subtly different. Let's make it fair: ====== % proc fw_2 {count args} {linsert [string repeat "$args " $count] 0} % time {fw_2 123 x y z} 10000 ;# 60.4778 microseconds per iteration ====== This version forces its result to be a pure list. And wow, despite being "less efficient", [FW]'s dalliance with strings is still faster than any of the list manipulation approaches that had preceded it. That's quite impressive. I believe the reason is that it avoids [[[eval]]] and all Tcl-based looping. It's just two commands, and almost no work is done in [TEBC]. ---- '''List equality test''' independent of whitespace outside of elements: Taken from [A little XML parser] where you can find other things to do with lists ====== proc lequal {a b} { if {[llength $a] != [llength $b]} {return 0} if {[lindex $a 0] == $a} {return [string equal $a $b]} foreach i $a j $b {if {![lequal $i $j]} {return 0}} return 1 } ;# RS ====== [HaO] 2014-09-16: [aspect] proposed on the chat: ======tcl [list {*}$l1] eq [list {*}$l2] ====== '''Check if combination of list elements is valid''' against a list of lists, [JM] 2004-01-04: this code relies on 'lequal' ====== set thisCase [list a c b] set lstValid { {a b c} {a a c} {a b b} {a a a} } ====== ====== proc chkValidCombination {lstValid thisCase} { set valid 0 foreach validCase $lstValid { set equal [lequal $validCase $thisCase] if {$equal} {set valid 1} } return $valid } puts [chkValidCombination $lstValid $thisCase] ====== ---- '''Keylist access:''' Data arranged as alternating ''key value''... can be searched like this, where non-existing keys just return an empty list: ====== proc keyget {list key} { foreach {lkey value} $list { if [string equal $lkey $key] {return $value} } } ;# RS % keyget {fnm John lnm Brown phone (123)456-7890 email john@brown.com} phone (123)456-7890 % keyget {fnm John lnm Brown phone (123)456-7890 email john@brown.com} fax ====== ---- '''Insert element into sorted list''' at suitable position: ====== proc linsertsorted {list newElement} { set pos 0 foreach element $list { if {$element > $newElement} break incr pos } linsert $list $pos $newElement } ;# RS -- testing: ====== ======none % linsertsorted {a b c d e} f a b c d e f % linsertsorted {a b c d e} 0 0 a b c d e % linsertsorted {a b c d e} aa a aa b c d e ====== [DKF] notes that this is the most efficient way to maintain a sorted list of things with occasional insertions of elements. The alternative - append and full resort - is much more costly as the list size increases. [jcw] 2004-10-04: Let me split hairs here. What you end up with is "insertion sort", not the most efficient sort algorithm in the world. For single, incidental inserts: yes, good approach. But if the insertions come in bursts, it's not optimal. One could collect insertions, and resort lazily on first access. Implementation left as exercise for the reader (heh!). [AF]: here is my implementation of a BINARY insertion sort: ====== proc BinaryInsert {list pattern} { set lo -1 set hi [llength $list] set test [expr {$hi / 2}] while {$lo != $test} { set res [string compare -nocase [lindex $list $test] $pattern] if {$res < 0} { set lo $test } elseif {$res > 0} { set hi $test } else { return [linsert $list $test $pattern] } set test [expr {($hi + $lo) / 2}] } return [linsert $list $hi $pattern] } ====== ---- '''Swap a paired list''': e.g. dictionaries, string maps, x/y coordinates... ====== proc lswap list { set res {} foreach {a b} $list {lappend res $b $a} set res } ;# RS % lswap {a b c d e f g h} b a d c f e h g ====== ---- '''List intersection:''' For a number of lists, return only those elements that are present in all lists: ====== proc intersect args { set res {} foreach element [lindex $args 0] { set found 1 foreach list [lrange $args 1 end] { if {[lsearch -exact $list $element] < 0} { set found 0; break } } if {$found} {lappend res $element} } set res } ;# RS ====== [kpv] 2018-10-24: here's a one-liner using [lmap] for intersecting two lists: ====== set intersect [lmap a $alist {if {$a in $blist} {set a} else continue}] ====== [RS] 2015-05-13: a simpler take for two lists, using the [in] operator: ====== } ====== [RKzn] 2016-09-28: the previous proc works provided the first list does not have duplicate elements. Otherwise all elements from the first list that match at least one element from the second list will be included in the result: ====== tcl> lintersect {a b} {a c} a tcl> lintersect {a a b} {a c} a a ====== By the way, lists without duplicates (or ignoring the ones that may exist) can be seen as sets. For those, there are implementations for intersection in [tcllib]: '::[struct::set] intersect' and '::struct::set intersect3' inList2: Name of the list in which to put list2 only elements inBoth: Name of the list in which to put elements in list1 & list2 ====== proc intersect3 {list1 list2 inList1 inList2 inBoth} { upvar $inList1 in1 upvar $inList2 in2 upvar $inBoth inB set in1 [list] set in2 [list] set inB [list] set list1 [lsort $list1] set list2 [lsort $list2] # Shortcut for identical lists is faster if { $list1 == $list2 } { set inB $list1 } else { set i 0 foreach element $list1 { if {[set p [lsearch [lrange $list2 $i end] $element]] == -1} { lappend in1 $element } else { if { $p > 0 } { set e [expr {$i + $p -1}] foreach entry [lrange $list2 $i $e] { lappend in2 $entry } incr i $p } incr i lappend inB $element } } foreach entry [lrange $list2 $i end] { lappend in2 $entry } } } ;# David Easton ====== ---- '''Prepend elements to a list''' (add in front): ====== proc lprepend {var args} { upvar 1 $var v set v [eval [list linsert $v 0] $args] } ;# DKF ====== [TR]: You can also use `[lreplace]` where the first index is -1 and the second is -2 ... like so: ====== set myList [list 0 1 2] set myList [lreplace $myList -1 -2 5] #-> 5 0 1 2 ====== ---- [GPS] 2003: In the [Tcl Chatroom] I came up with this idea. You may find it easier than using lreplace to do the same. ====== proc remove.list.item {lPtr i} { upvar $lPtr l; set l [lreplace $l $i $i] } ====== Example: ======none % set l [list a b c] a b c % remove.list.item l 1 a c % set l a c ====== ---- '''Key-value list searching''': Before [dict] arrived, we could have a two-way map key<->value like this: ====== proc kvsearch {kvlist item} { set pos [lsearch $kvlist $item] if {$pos != -1} { lindex $kvlist [expr {$pos+1-2*($pos%2)}] } } ;# RS % kvsearch {1 one 2 two 3 three} four ;# returns empty string/list % kvsearch {1 one 2 two 3 three} 1 one 0 % kvsearch {1 one 2 two 3 three} one 1 ====== ---- '''Pairs''' of members of a list: ====== proc pairs set { set res {} set last [expr {[llength $set]-1}] for {set ia 0} {$ia < $last} {incr ia} { foreach b [lrange $set [expr {$ia+1}] end] { lappend res [list [lindex $set $ia] $b] } } set res } ;# RS % pairs {a b c d} {a b} {a c} {a d} {b c} {b d} {c d} ====== Simpler: ====== proc pairs set { set res {} foreach a [lrange $set 0 end-1] { set set [lrange $set 1 end] foreach b $set {lappend res [list $a $b]} } set res } ;# RS ====== ---- '''In-place queues''' using the [K] combinator ====== proc K {a b} {set a} ## # Pop an item off a list, left or right # proc lpop {how listName} { upvar $listName list switch -- $how { right { K [lindex $list end] [set list [lrange $list 0 end-1]] } left { K [lindex $list 0] [set list [lrange $list 1 end]] } default { return -code error {lpop right|left listName} } } } ## # Pop an item onto a list, left or right # proc lpush {how listName item} { upvar $listName list switch -- $how { right { lappend list $item } left { set list [linsert [K $list [set list {}]] 0 $item] } default { return -code error "lpush right|left listName item" } } } ====== See also [Stacks and queues], [Implementing FIFO queues] and [Tcllib]'s [stack] and [queue]. ---- '''Flatten a list''' of any depth, i.e. remove all grouping: Use `[[::struct::list flatten]` in [tcllib] ====== ::struct::list flatten ?-full? ?--? sequence ====== The subcommand takes a single sequence and returns a new sequence where one level of nesting was removed from the input sequence. In other words, the sublists in the input sequence are replaced by their elements. The subcommand will remove any nesting it finds if the option -full is specified. ======none % ::struct::list flatten {1 2 3 {4 5} {6 7} {{8 9}} 10} 1 2 3 4 5 6 7 {8 9} 10 % ::struct::list flatten -full {1 2 3 {4 5} {6 7} {{8 9}} 10} 1 2 3 4 5 6 7 8 9 10 ====== But note that it may be inconsistent or otherwise counterintuitive: ====== % ::struct::list flatten -full {1 2 3 {4 5} {6 7} {{8 9}} 10} 1 2 3 4 5 6 7 8 9 10 % ::struct::list flatten -full {1 2 3{4 5} {6 7} {{8 9}} 10} 1 2 3\{4 5\} 6 7 8 9 10 % ::struct::list flatten -full {1 2 3 {4 5}{6 7} {{8 9}} 10} list element in braces followed by "{6" instead of space ====== If '''3\{4 5\}''' then why not '''\{4 5\}\{6 7\}''' or even '''3 4 5''' and '''4 5 6 7'''? Because `3{4` and `5}` are syntactically valid, which `{4 5}{6` isn't (the closing brace that closes the initial opening brace isn't the last character in the word). `3{4` and `5}` can't be transformed into `3 4 5` since that would change the data content. ======note [HaO] 2014-09-16: One may use 'concat {*}' to flatten a matrix by one level: ======tcl % concat {*}{1 2 3 {4 5} {6 7} {{8 9}} 10} 1 2 3 4 5 6 7 {8 9} 10 ====== ---- If 3\{4 5\} then why not \{4 5\}\{6 7\} or even 3 4 5 and 4 5 6 7? [MAK]: Perhaps belongs in [Additional string functions], but: This function takes a list of lists representing cell information for a table (i.e., each element of the top-level list is a row of data, and each element of those are individual columns of data) and generates text output with all of the columns aligned with each other. By default a single space is output between the longest cell and the next one; extra spaces can be added through the optional padding argument. ====== proc listToTable { in {padding 0} } { set result {} array set lengths {} # Determine the longest element in each column foreach line $in { set colnum 1 foreach column $line { set length [string length $column] if {[info exist lengths($colnum)]} { if {$lengths($colnum) < $length} { set lengths($colnum) $length } } else { set lengths($colnum) $length } incr colnum } } # Format the output foreach line $in { set colnum 1 set maxcol [llength $line] foreach column $line { if {$colnum < $maxcol} { append result [ format %-*s [ expr {$lengths($colnum) + 1 + $padding}] $column] } else { append result $column } incr colnum } append result "\n" } return $result } ====== Example: ======none % listToTable {a {aaaa bb cccccc} {aaaaaa bbbbbbb cc ddddddd} {a b c d}} a aaaa bb cccccc aaaaaa bbbbbbb cc ddddddd a b c d ====== ---- [AMG]: [interleave] lets you combine parallel lists so you can pass them to [[array set]]. [[listc]] and [[[lcomp]]] provide [list comprehension]s. ---- [Sarnold]: A command for '''splitting one list into segments''' Instead of doing: ====== set beginning [lrange $list 0 end-$size] set end [lrange $list end-[expr {$size-1}] end] ====== write more understandable things like: ====== foreach {beginning end} [lrange -split $list end-$size] {break} ====== Of course, it may be implemented in pure tcl... ---- Ok, so I'd propose also my extensions. '''Selects elements of a list on given positions and return them as a list'''. ======none %set a {one two three four five} ... %lselect $a 0 3-4 one four five ====== ====== proc lselect {list args} { set result {} foreach i $args { set range [split $i -] if { [llength $range] == 2 } { mset {from to} $range for {set n $from} {$n <= $to} {incr n} { lappend result [lindex $list $n] } continue } lappend result [lindex $list $i] } return $result } ====== '''Splitting list at index:''' ====== proc lsplit {ls index} { return [ list [ lrange $ls 0 [expr {$index-1}]] [ lrange $ls $index end]] } ====== Functional extensions: '''Filter each element through given command and return them as a list:''' ====== proc filter {list cmd} { set result {} foreach i $list { lappend result [eval "$cmd {$i}"] } return $result } ====== ======none %set a { { 1 } { 2 } { 3 } } ... %filter $a "string trim" 1 2 3 ====== [HaO] see [lmap] (new in tcl8.6) '''Return a list of elements that satisfy given predicate:''' ======none % set l {0 5 3 4 2} 0 5 3 4 2 % select $l {expr 2<} 5 3 4 ====== ====== proc select {list pred} { set result {} foreach i $list { if {[eval $pred [list $i]]} {lappend result $i} } return $result } ====== [MG] offers an alternative version, that uses `[uplevel]` to evaluate `$pred` in the caller's scope, and also uses `[string map]` to allow the value being checked to placed anywhere in it (as '##') - it's called inside `[expr]`. The only reason it uses `##` as the placeholder for the value is because I couldn't think of a ''good'', more Tcl'ish way to do it, and that's what's used in another language I use. If someone can think of a good way to do it that fits more with the Tcl way, please change it. ====== proc select2 {list pred} { set result [list] foreach i $list { if {[uplevel 1 [list expr [string map [list ## $i] $pred]]]} { lappend result $i } } return $result; } ====== ======none % set list1 {a b c d e} a b c d e % set list2 {c d e f g} c d e f g % select2 $list1 {[lsearch $list2 ##]>-1} c d e ====== [Lars H] thinks the Tcl way to do it is to have a variable that contains list item to consider, thus: ====== proc select3 {var expr list} { upvar 1 $var item set res {} foreach item $list { if {[uplevel 1 [list ::expr $expr]]} then { lappend res $item } } return $res } ====== Example: ======none % select3 s {[string is integer $s]} {0 3 x 0x3 09 35 -7 0. 000 1e3} 0 3 0x3 35 -7 000 % select3 s {$s != 0} {0 3 x 0x3 09 35 -7 0. 000 1e3} 3 x 0x3 09 35 -7 1e3 ====== Having the list last makes it easy to define aliases: ======none % interp alias {} nonzero {} select3 s {$s!=0} % nonzero {0 3 x 0x3 09 35 -7 0. 000 1e3} 3 x 0x3 09 35 -7 1e3 ====== [NEM] 2008-02-17: Would call the `filter` above `[map]`, and `select` would be `[filter]`. I agree with [Lars H] about taking the list argument last (the [tcllib] version don't do this, alas). As an example: ====== proc filter {p xs} { set ys [list] foreach x $xs {if {[uplevel #0 $p [list $x]]} {lappend ys $x}} return $ys } # Usage: set xs {0 3 x 0x3 09 35 -7 0. 000 1e3} filter {string is integer} $xs # Simple aliases: proc let {name = args} {interp alias {} $name {} {*}$args} let integers = filter {string is integer} integers $xs ;# Same result ====== More complex expressions can easily be handled by [lambda]s: ====== proc func {p b} {list ::apply [list $p [list expr $b]]} filter [func x {$x != 0}] $xs ====== ---- [FW]: '''A more versatile key-value search''' This function allows for searching an associative `[dict]`/`[array]`-style list, with the added feature that the length of each "row" can be anything (instead of just 2: ''key value'') and you can pick which sub-index is used for the key and for the value to retrieve. The first argument is the list, the second is the key to search for. Optional args: the third (default 2) is the length of each row, the fourth (default 0) is the index within the row of the key, and the fifth (default 1) is the index within the row of the value to retrieve. This proc requires an `[lrepeat]` proc (as offered above; I've included one here for completeness). ====== proc lrepeat {val num} { set res [list] for {set i 0} {$i < $num} {incr i} {lappend res $val} return $res } proc lassoc {list key {rowsize 2} {keyind 0} {valind 1}} { foreach [lreplace [lreplace [lrepeat nullvar $rowsize] \ $keyind $keyind qkey] $valind $valind qval] $list { if {[string equal $qkey $key]} {return $qval} } return -code error {No match found.} } ====== Example: ====== # English, Dutch, French set phrases [list \ Hi Hallo Bonjour \ {I'll have the soup.} {Ik geef opdracht tot de soep.} \ {J'achèterai le potage} \ Bye {Tot ziens} {Au revoir}] puts [lassoc $phrases Hi 3 0 2] ;# English to French ====== ---- [Sarnold]: I would like to filter elements when walking a list with `foreach`. Something like this: ====== foreach-filter x {$x > 0} $list {puts "$x is positive"} ====== This improves over list comprehension for cases we do not want to walk the whole list. (foreach is lazy) [AK]: I have no idea what you mean by 'foreach is lazy'. Can you elaborate ? `[struct::list::]::filterfor` is very similar, modulo arrangement of the arguments, and not using a script body [Sarnold]: I admit I abused the term 'lazy' but I meant that, in the following: ====== foreach x [filter $hugelist cmd] { if {[somecmd $x]} break } ====== the hugelist has to be filtered completely before the foreach is invoked, because of Tcl's eager evaluation. And the huge list is transformed even if only one item is processed and the foreach loop is exited (via break). But the same treatment could be optimized with the proposed foreach-filter: ====== foreach-filter x cmd $hugelist { if {[somecmd x]} break } ====== Compared with the first version, it does not have to process $hugelist totally, like Haskell's list filters. (And Haskell works with ''lazy'' evaluation) We could build a similar foreach-map command. [AK]: Ok, now I understand. Both Tcl using 'strict' evaluation and the use case you are looking for. Another possibility, but way more complex for the internals would be the introduction of generators. Although, with Tcl 8.6's coroutines we have a way of doing that already. Have the filter be a coroutine which yields each element as requested. Still, foreach is not prepared to ask for elements one by one, it will always take the whole list. So even that is not yet a workable way of partial processing of a computed/infinite list. [LV]: I am not certain, but would the [foreach async] discussion be a way of interacting with the computed infinite generated lists? If so, then is this perhaps something that could appear in [tcllib]'s [control] module for use with Tcl 8.6? [MR]: Wouldn't following suffice (unless Haskell-like / generators-like semantics are really required) ? ====== foreach x $lst { if {![predicate $x]} continue if {whatever} break we_can_do_whatever_we_want_with $x now } ====== Naive implementation of foreach_filter would be: ====== proc foreach_filter {varName lst predicate cmd} { uplevel 1 [list foreach $varName $lst [list if $predicate $cmd]] } ====== which, for the following test script: ====== foreach_filter x {aa bb ab ac} {[string index $x 0] == {a}} { puts $x if {$x == {ab}} break } ====== yields following output: ======none aa ab ====== ie. `bb` is skipped by the filter and after encountering/printing `ab` `[break]` kicks in (hallelujah for Tcl metaprogramming !!! ;-)) [YOSIFOV]: http://balkansoft.blogspot.ru/2012/10/traversing-over-paths.html%|%Original is here%|% Walking on paths (like MS-DOS paths, but each path should be list of dirs, not one string): ====== proc forpaths {boundVarNames paths body} { # walk on paths, each is list of dirs. $body will execute on visit each dir, # variables bound: # $keyName - current path # $levelName - current level (0...N) # $leafName - is leaf or not (1, 0) foreach {keyName levelName leafName} [lrange $boundVarNames 0 2] {} set group [dict create] foreach path $paths { dict set group {*}$path @LEAF } proc _cmp {a b} { if {[expr {$a > $b}]} { return 1 } elseif {[expr {$a < $b}]} { return -1 } else {return 0} } proc _trackpath {track level dir} { if {$track eq {}} {set track [list @DUMMY]} switch -- [_cmp [expr $level+1] [llength $track]] { 1 {lappend track $dir 0 {lset track end $dir} -1 {set track [lreplace $track $level end $dir]} } return $track } set gtrack {}; # current path when visit each node proc _walk {d keyName levelName leafName body {_deep 2}} { # here $level is level in tree, not in stack # $_deep is level in stack upvar $_deep $keyName key $levelName level upvar gtrack gtrack if {$leafName ne {}} { upvar $_deep $leafName leaf } dict for {k v} $d { set level [expr {$_deep-2}] set gtrack [_trackpath $gtrack $level $k] set key $gtrack if {$v eq @LEAF} { set leaf 1 uplevel $_deep $body } else { # nested set leaf 0 uplevel $_deep $body _walk $v $keyName $levelName $leafName $body [expr {$_deep+1}] } } } _walk $group $keyName $levelName $leafName $body } ====== And usage something like this: ====== forpaths {key level leaf} $dirs {...} # OR forpaths {key level} $dirs {...} # OR forpaths key $dirs {...} ====== ''Find the difference between two lists'' ====== proc ldiff {a b} { lmap elem $a { expr {$elem in $b ? [continue] : $elem} } } ====== ---- [AMG]: '''Sorting a list by element string length''' ====== lsort -command {apply {{a b} {expr {[string length $a] - [string length $b]}}}} $list ====== ---- '''[domino] - 2018-05-25 16:30:34''' (First time edit; forgive formatting and "where on the page" issues) Re: LPREPEND, couldn't you just use this? All produce the properly-appended lists (obeying listed-ness): --> "{10 11 12 13 14} 25 {100 101 102 103 104} {{10 11 12 13 14}} 0 1 2 3 4" Numbers given (in ms): ( 5 single iterations: quickest -> slowest) / ( time {code} 1000 [iterations] ) TCL8.6.7 ====== proc lprependDKF { var_name args } {